Pagini recente » Cod sursa (job #3150495) | Aplicatii, probleme | Monitorul de evaluare | Istoria paginii utilizator/hurjui12alexandru | Cod sursa (job #842392)
Cod sursa(job #842392)
program knutt_morris_pratt;
var f1,f2:text;
s1,s2:ansistring;
str:array [0..4000000] of char;
prefix,sol:array [0..4000000] of longint;
i,j,l1,l2,k:longint;
bufin,bufout:array [1..1000000] 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);
l1:=length(s1);
l2:=l1+length(s2)+1;
s2:=s1+'*'+s2;
for i:=1 to l2 do str[i-1]:=s2[i];
for i:=1 to l2 do
begin
j:=prefix[i-1];
while (j>0) and (str[i]<>str[j]) do
j:=prefix[j-1];
if str[i]=str[j] then inc(j);
prefix[i]:=j;
if j=l1 then begin
inc(k);
sol[k]:=i-2*l1;
end;
end;
writeln(f2,k);
i:=1;
while (i<=k) and (i<=1000) do
begin
write(f2,sol[i],' ');
inc(i);
end;
close(f1);close(f2);
end.