Cod sursa(job #177890)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 13 aprilie 2008 19:41:51
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.06 kb
var v,o:array[1..2001000]of char;
    pi,po:array[1..2000100]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);
   m:=1;
   while(ord(v[m])<>0)do
   m:=m+1;
{   while not eoln(f) do
   begin
   m:=m+1;
   read(f,v[m]);
   end;         }
   readln(f,o);
   n:=1;
   while(ord(o[n])<>0)do
   n:=n+1;
   n:=n-1;
   m:=m-1;
 {  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;
   assign(f,'strmatch.out');
   rewrite(f);
   writeln(f,k);
   if k>1000 then k:=1000;
   for i:=1 to k do
   write(f,po[i],' ');
   writeln(f);
   close(f);
end.