Pagini recente » Cod sursa (job #1667149) | Cod sursa (job #2008904) | Cod sursa (job #2605604) | Cod sursa (job #2265510) | Cod sursa (job #843359)
Cod sursa(job #843359)
program knutt_morris_pratt;
var f1,f2:text;
s1:array [0..2000000] of char;
s2:array [1..2000000] of char;
prefix1,prefix2:array [0..2000000] of longint;
i,j,k,l:longint;
rez:array [1..1000] of longint;
bufin,bufout:array [1..100000] of char;
begin
assign(f1,'strmatch.in');
reset(f1);
assign(f2,'strmatch.out');
rewrite(f2);
settextbuf(f1,bufin);
settextbuf(f2,bufout);
readln(f1,s1);
readln(f1,s2);
i:=1;
while s1[i] in['A'..'Z','a'..'z','0'..'9'] do
begin
j:=prefix1[i-1];
while (j>0) and (s1[i]<>s1[j]) do j:=prefix1[j-1];
if s1[i]=s1[j] then inc(j);
prefix1[i]:=j;
inc(i);
end;
l:=i;
i:=1;
while s2[i] in ['A'..'Z','a'..'z','0'..'9'] do
begin
j:=prefix2[i-1];
while (j>0) and (s2[i]<>s1[j]) do j:=prefix1[j-1];
if s2[i]=s1[j] then inc(j);
prefix2[i]:=j;
if j=l then
begin
inc(k);
if k<=1000 then rez[k]:=i-l;
end;
inc(i);
end;
writeln(f2,k);
if k<1000 then for i:=1 to k do write(f2,rez[i],' ')
else for i:=1 to 1000 do write(f2,rez[i],' ');
close(f1);
close(f2);
end.