Pagini recente » Cod sursa (job #804468) | Cod sursa (job #2693292) | Cod sursa (job #2740729) | Cod sursa (job #1797812) | Cod sursa (job #144225)
Cod sursa(job #144225)
var f1,f2:text;
s1,s2:ansistring;
i,h:longint;
v:array[0..1024] of longint;
pi:array[0..2000010] of longint;
procedure prefix(s:ansistring);forward;
procedure kmp(s1,s2:ansistring);
var i,n,m,p:longint;
begin
n:=length(s1);
m:=length(s2);
prefix(s1);
p:=0;
h:=0;
for i:=1 to m do
begin
while (p>0)and(s1[i]<>s2[p+1]) do
p:=pi[p];
if s1[i]=s2[p+1] then
inc(p);
if p=n then
begin
inc(h);
p:=pi[p];
if h<=1000 then
v[h]:=i-n;
end;
end;
end;
procedure prefix(s:ansistring);
var i,n,p:longint;
begin
n:=length(s);
pi[1]:=0;
p:=0;
for i:=2 to n do
begin
while (p>0)and(s[i]<>s[p+1]) do
p:=pi[p];
if s[i]=s[p+1] then
inc(p);
pi[i]:=p;
end;
end;
begin
assign(f1,'strmatch.in');
reset(f1);
assign(f2,'strmatch.out');
rewrite(f2);
readln(f1,s1);
readln(f1,s2);
kmp(s1,s2);
writeln(f2,h);
if h>1000 then
h:=1000;
for i:=1 to h-1 do
write(f2,v[i],' ');
if h>0 then
writeln(f2,v[h]);
close(f1);
close(f2);
end.