caiweiwenjs 2008-12-08 02:54:00
点我顶贴
收藏
删除
KMP算法!
program rqnoj382；
var
s1,s2:ansistring；
p,a:array[1..100000] of longint；
i,j,len1,len2,ans:longint；
begin
readln(s1)；
readln(s2)；
len1:=length(s1)；
len2:=length(s2)；
p[1]:=0；
j:=0；
for i:=2 to len1 do
begin
while (j>0)and(s1[j+1]<>s1[i]) do j:=p[j]；
if s1[j+1]=s1[i] then inc(j)；
p[i]:=j；
end；
ans:=0；
j:=0；
for i:=1 to len2 do
begin
while (j>0)and(s2[i]<>s1[j+1]) do j:=p[j]；
if s1[j+1]=s2[i] then inc(j)；
if j=len1 then
begin
inc(ans)；
a[ans]:=i-len1+1；
j:=p[j]；
end；
end；
if ans<>0 then
begin
writeln(ans)；
for i:=1 to ans do
writeln(a[i])；
end
else
writeln(’There must be something wrong.’)；
end.