Cod sursa(job #932947)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 29 martie 2013 13:53:04
Problema Potrivirea sirurilor Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.94 kb
program kmp;
var f,g:text;
    a,b:ansistring;
    n,m,i:longint;
    k:longint;
    nr:longint;
    v:array[1..200000] of longint;
    x:array[1..200000] of longint;
    bufin,bufout:array[1..65000] of byte;

procedure prefix;
var k:longint;
begin
 k:=0; x[1]:=0;
 for i:=2 to n do
 begin
  while (k>0) and (a[i]<>a[k+1]) do
   k:=x[k];
  if a[i]=a[k+1] then inc(k);
  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);
 n:=length(a);
 m:=length(b);
 prefix;
 k:=0;
 for i:=1 to m do
 begin
  while (k>0) and (b[i]<>a[k+1]) do
   k:=x[k];
  if b[i]=a[k+1] then
   inc(k);
  if k=n then
  begin
   inc(nr);
   if nr<1001 then
    v[nr]:=i-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.