题目大意
给定两个字符串a,b
求a在b中出现了多少次
分析
裸的kmp，不懂的可以去看一下
http://www.matrix67.com/blog/archives/115此乃大神
直接水过
代码
var
p:array
[1..2000000] of longint;
i,
j,k:longint;
a,b:ansistring;
l,z:longint;
n,m:longint;
ans:longint;
begin
readln(l);
for z:=
1 to l do
begin
readln(b);
readln(a);
n:=
length(a);
m:=
length(b);
p
[1]:=
0;
P
[1]:=
0;
j:=
0;
for i:=
2 to m do
begin
while (
j>
0) and (b
[j+1]<>b
[i]) do
j:=p
[j];
if b
[j+1]=b
[i] then
j:=
j+
1;
p
[i]:=
j;
end;
ans:=
0;
j:=
0;
for i:=
1 to n do
begin
while (
j>
0) and (b
[j+1]<>a
[i]) do
j:=p
[j];
if b
[j+1]=a
[i]
then
j:=
j+
1;
if j=m then
begin
ans:=
ans+
1;
j:=p
[j];
end;
end;
writeln(
ans);
end;
end.
转载请注明原文地址: https://ju.6miu.com/read-1295909.html
