Cod sursa(job #1420314)

Utilizator ButnaruButnaru George Butnaru Data 18 aprilie 2015 10:26:12
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.89 kb
program stringmatching;
type buf=array[0..1 shl 17] of char;
     vector1=array[0..2000001] of longint;
     vector2=array[0..1001] of longint;
var s,ss:ansistring; urm:vector1;
    ff1,ff2:buf; sol:vector2;
    n,m,i,j,nr,k: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);
k:=0; urm[1]:=0; nr:=0;
for i:=2 to n do begin
while (k>0) and (s[i]<>s[k+1]) do k:=urm[k];
if s[i]=s[k+1] then k:=k+1;
urm[i]:=k;
end;
k:=0;
for i:=1 to m do begin
while (k>0) and (ss[i]<>s[k+1]) do k:=urm[k];
if ss[i]=s[k+1] then k:=k+1;
if k=n then begin
nr:=nr+1;
if nr<=1000 then sol[nr]:=i-k;
k:=urm[k];
end;
end;
writeln (f2,nr);
if nr>1000 then nr:=1000;
for i:=1 to nr do write (f2,sol[i],' ');
close (f1);
close (f2);
end.