Cod sursa(job #292239)

Utilizator lexu93Todor Alex lexu93 Data 30 martie 2009 21:45:22
Problema Potrivirea sirurilor Scor 100
Compilator fpc Status done
Runda The Beginners Marime 2.5 kb
var v,o:array[1..2001000]of char;      
    pi,po:array[1..2000100]of longint;      
    m,n,i,k,q:longint;      
    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.    
var v,o:array[1..2001000]of char;   
    pi,po:array[1..2000100]of longint;   
    m,n,i,k,q:longint;   
    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.