Cod sursa(job #177880)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 13 aprilie 2008 19:18:14
Problema Potrivirea sirurilor Scor 14
Compilator fpc Status done
Runda Arhiva educationala Marime 0.95 kb
var v,o:array[0..20000000]of char;
    pi,po:array[0..20000000]of longint;
    m,n,i,j,k,p,l,pu,q:longint;
    b,u:int64;
    c:char;
    f:text;
begin
   assign(f,'strmatch.in');
   reset(f);
   readln(f,v);
{   while not eoln(f) do
   begin
   m:=m+1;
   read(f,v[m]);
   end;         }
   readln(f,o);
 {  while not eoln(f) do
   begin
   n:=n+1;
   read(f,o[n]);
   end;     }
   close(f);
   pi[1]:=0;
   k:=0;
   for i:=2 to m do
   begin
   while(k>0)and(v[k+1]<>v[i])do
   k:=pi[k];
   if v[k+1]=v[i] then k:=k+1;
   pi[i]:=k;
   end;
   q:=0;
   k:=0;
   for i:=1 to n do
   begin
   while(q>0)and(v[q+1]<>o[i])do
   q:=pi[q];
   if v[q+1]=o[i] then q:=q+1;
   if q=m then begin k:=k+1;
                     po[k]:=i-m;
               end;
   end;
   if k>1000 then k:=1000;
   assign(f,'strmatch.out');
   rewrite(f);
   writeln(f,k);
   for i:=1 to k do
   write(f,po[i],' ');
   writeln(f);
   close(f);
end.