Cod sursa(job #699896)

Utilizator promix2012petruta andrei promix2012 Data 29 februarie 2012 21:52:47
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 1 kb
program kmp;
const fi='strmatch.in';
      fo='strmatch.out';
var f,g:text;
bufin,bufout:array[1..65000] of byte;
urm:array[1..200000] of longint;
v:array[1..1000] of longint;
nr,i,j,k,m,n:longint;
s,t:ansistring;
procedure creare_pref;
begin
k:=0;
urm[1]:=0;
for i:=2 to m do
   begin
   while (k>0)and(s[i]<>s[k+1]) do
        k:=urm[k];
   if s[i]=s[k+1] then
      inc(k);
   urm[i]:=k;
   end;
end;
begin
assign(f,fi);
reset(f);
settextbuf(f,bufin);
assign(g,fo);
rewrite(g);
settextbuf(g,bufout);
readln(f,s);
readln(f,t);
m:=length(s);
n:=length(t);
creare_pref;
k:=0;
for j:=1 to n do
  begin
     while (k>0)and(t[j]<>s[k+1]) do
        k:=urm[k];
     if t[j]=s[k+1] then
         inc(k);

     if k=m then
         begin
         inc(nr);
         if nr<1001 then
         v[nr]:=j-k;
         k:=urm[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.