Cod sursa(job #293798)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 2 aprilie 2009 08:19:11
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>   
#include<string.h>   
using namespace std;   
char a[2000010],b[2000010];   
int n,m,i,q,pi[2000010],sol,v[1010],k;   

int main()   
{   
  
ifstream f("strmatch.in");   
ofstream g("strmatch.out");   
  
f.get(a+1,2000005); f.get();   
f.get(b+1,2000005);   

n=strlen(a+1);

k=0; pi[1]=0;

 for(i=2;i<=n;i++)

  { while ( (k>0) && (a[k+1]!=a[i]) )

    k=pi[k];

	if(a[k+1]==a[i])
	  k++;

	pi[i]=k;
  }

m=strlen(b+1);
  
q=0;   
  
 for(i=1;i<=m;i++)   
  
  { while( (q>0) && (a[q+1]!=b[i]) )   
  
     q=pi[q];   
  
    if(a[q+1]==b[i])   
     q++;   
  
    if(q==n)  { sol++; if(sol<=100) v[sol]=i-n;}   
  }   
g<<sol<<'\n';   
if(sol>1000) sol=1000;   
for(i=1;i<=sol;i++) g<<v[i]<<" ";   
  
f.close();   
g.close();   
return 0;   
}