Cod sursa(job #747809)

Utilizator andrei_toaderToader Andrei Sorin andrei_toader Data 11 mai 2012 22:45:25
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.88 kb
program kmp;
var f,g:text;
    a,b:ansistring;
    m,n,i,k,nr:longint;
    x:array [1..200000] of longint;
    bufin,bufout:array [1..65000] of byte;
    v:array [1..1005] of longint;

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