Pagini recente » Cod sursa (job #1767230) | Cod sursa (job #2688425) | Cod sursa (job #1431267) | Cod sursa (job #2335323) | Cod sursa (job #1405480)
//KMP//
program stringmatching;
type tabel=array[0..1001] of longint;
tabb=array[0..2000001] of longint;
buf=array[0..1 shl 17] of char;
var sol:tabel; urm:tabb;
ff1,ff2:buf;
s,ss:ansistring;
n,m,i,j,k,nr:longint;
f1,f2:text;
begin
assign (f1,'strmatch.in');
assign (f2,'strmatch.out');
reset (f1);
rewrite (f2);
settextbuf(f1,ff1);
settextbuf(f2,ff2);
readln (f1,s);
readln (f1,ss);
n:=length(s); m:=length(ss); urm[1]:=0; k:=0;
for i:=2 to n do begin
while (k>0) and (s[k+1]<>s[i]) do k:=urm[k];
if s[k+1]=s[i] then k:=k+1;
urm[i]:=k;
end;
k:=0;
for i:=1 to m do begin
while (k>0) and (s[k+1]<>ss[i]) do k:=urm[k];
if s[k+1]=ss[i] then k:=k+1;
if k=n then begin
nr:=nr+1; sol[nr]:=i-n+1;
k:=urm[k];
end;
if nr=1000 then break;
end;
writeln (f2,nr);
for i:=1 to nr do write (f2,sol[i]-1,' ');
close (f1);
close (f2);
end.