Cod sursa(job #870711)

Utilizator ion824Ion Ureche ion824 Data 3 februarie 2013 20:29:25
Problema Potrivirea sirurilor Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
#include<string>
using namespace std;
const int NM=200005;
string T,P;
int z[NM+NM];

int main(){
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    int N,i,j,l,L,r,p,k,M,nr=0;
    
    getline(fin,P); getline(fin,T); M=P.length();

    P=" "+P+"$"+T; L=P.length()-1;

    z[1]=0; l=r=0;
    for(i=2;i<=L;++i)
    {
      if(i>r){ 
              k=0; 
              while(P[k+1]==P[i+k]  && i+k<=L)++k;
              z[i]=k;
              if(k>0){ l=i; r=l+k-1; }         
               } 
        else
          if(z[i-l+1]< (r-i+1)) z[i]=z[i-l+1];
            else
            {
              z[i]=z[i-l+1];
              k=0;
              while(P[r+k+1]==P[k+z[i]+1])++k;
              z[i]+=k;
              if(k>0){ l=i; r=l+k-1; } 
            }           
        }                 
    
   //for(i=1;i<=L;++i)fout<<z[i]<<' ';
   
   for(i=M+1;i<=L;++i)if(z[i]==M)++nr;
   fout<<min(nr,1000)<<'\n'; 
   for(i=M+1;i<=L && nr;++i)if(z[i]==M){ --nr; fout<<i-M-2<<" "; }
 return 0;   
}