Cod sursa(job #299477)

Utilizator llobyLodoaba Mihai lloby Data 6 aprilie 2009 19:59:25
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 1.12 kb
Program kmp;
type vec=array[0..256] of integer;
     poz=array[1..1000] of integer;
var s,x: string;
    i,p: integer;
    c: poz;
    t: text;
Function prefix(x: string): vec;
var m,k,i: longint;
    v: vec;
begin
    m:=length(x);
    v[1]:=0;
    k:=0;
      for i:=2 to m do
       begin
         while(k>0) and (x[k+1]<>x[i]) do
          k:=v[k];
         if x[k+1]=x[i] then k:=k+1;
         v[i]:=k;
       end;
    prefix:=v;
end;
Procedure KMP(s,x: string);
var m,n,i,j,q: longint;
    v: vec;
begin
  n:= length(s);
  m:=length(x);
  v:=prefix(x);
  q:=0;
  p:=0;
  for i:=1 to n do
    begin
      while (q>0) and (x[q+1]<>s[i]) do
        q:=v[q];
       if x[q+1]=s[i] then q:=q+1;
       if q=m then
                begin
                   p:=p+1;
                   c[p]:=i-m;
                   q:=v[q];
                end;
    end;
end;
begin
   assign(t,'strmatch.in'); reset(t);
   read(t,s);
   readln(t);
   read(t,x);
   close(t);
   KMP(s,x);
   assign(t,'strmatch.out'); rewrite(t);
   writeln(t,p);
   for i:=1 to p do
     write(t,c[i],' ');
   close(t);
end.