Cod sursa(job #709446)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 8 martie 2012 09:25:12
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.82 kb
program kmp;
var f,g:text;
a,b:ansistring;
v:array[1..1000] of longint;
x:array[1..2000000] of longint;
k,i,j,m,n,nr:longint;
bufin,bufout:array[1..65000]of byte;

procedure prefix ;
begin
k:=0; x[1]:=0;
for i:=2 to m do
begin
while (k>0) and (a[i]<>a[k+1]) do
k:=x[k];
if a[i]=a[k+1] then
k:=k+1;
x[i]:=k;
end;
end;

begin
assign (f,'strmatch.in'); reset (f);
assign (g,'strmatch.out'); rewrite (g);
settextbuf(f,bufin); settextbuf (g,bufout);
readln (f,a); read (f,b);
m:=length (a); n:=length (b);
prefix;
k:=0;
for j:=1 to n do
begin
while (k>0) and (b[j]<>a[k+1]) do
k:=x[k];
if b[j]=a[k+1] then
k:=k+1;
if k=m then
begin
nr:=nr+1;
if nr<1001 then
v[nr]:=j-k;
k:=x[k];
end;
end;
writeln (g,nr);
if nr>1000 then
nr:=1000;
for i:=1 to nr do
write (g,v[i],' ');
close (f); close (g);
end.