Cod sursa(job #177876)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 13 aprilie 2008 19:12:50
Problema Potrivirea sirurilor Scor 40
Compilator fpc Status done
Runda Arhiva educationala Marime 0.92 kb
var v,o:array[0..2000000]of char;
    pi,po:array[0..2000000]of longint;
    m,n,i,j,k,p,l,pu,q:longint;
    b,u:int64;
    c:char;
    f:text;
begin
   u:=0;
   assign(f,'strmatch.in');
   reset(f);
   while not eoln(f) do
   begin
   m:=m+1;
   read(f,v[m]);
   end;
   readln(f);
   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.