Cod sursa(job #1180894)

Utilizator DjokValeriu Motroi Djok Data 1 mai 2014 12:37:04
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 0.92 kb
var a,b:ansistring;
    n,m,i,q,nr,k:longint;
    rs,kmp:array[1..2000002] of longint;
    bif,bof:array[1..1 shl 16] of char;

begin
 assign(input,'strmatch.in');
 assign(output,'strmatch.out');
 reset(input);
 rewrite(output);
 settextbuf(input,bif);
 settextbuf(output,bof);

  readln(a); readln(b);
  n:=length(a); m:=length(b);

  for i:=2 to n do
   begin
    while (k>0) and (a[i]<>a[k+1]) do
     k:=kmp[k];
    if a[k+1]=a[i] then inc(k);
    kmp[i]:=k;
   end;

  for i:=1 to m do
   begin
    while (q>0) and (b[i]<>a[q+1]) do
     q:=kmp[q];
     if a[q+1]=b[i] then inc(q);
     if q=n then begin
                  inc(nr);
                  if nr<=1000 then rs[nr]:=i-n;
                  q:=kmp[q];
                 end;
   end;

  writeln(nr);

   if nr>1000 then nr:=1000;
    for i:=1 to nr do
     write(rs[i],' ');

 close(input);
 close(output);
{Totusi este trist in lume}
end.