Cod sursa(job #1117104)

Utilizator alinutzVasiu Alin alinutz Data 23 februarie 2014 01:20:57
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.03 kb
program kmp;
var f,g:text;
   bufin,bufout:array[1..65000]of byte;
   urm:array[1..2000000] 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,'strmatch.in'); reset(f);     settextbuf(f,bufin);
     assign(g,'strmatch.out'); 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.