Cod sursa(job #1135526)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 7 martie 2014 22:56:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<string>

using namespace std;
const int maxn = 2000005;
string s, t;
int a[maxn],x[maxn];

void make_prefix(){
	
	 int k=0,n=0,m=t.size();
  
    
    
    for(int i=1;i<m;i++){
    	while(k && t[k]!=t[i])k=a[k];
    	if(t[k]==t[i])k++;
    	a[i]=k;
    }
}

main(){
	ifstream fin("strmatch.in");
	ofstream fout("strmatch.out");
	
	fin>>t>>s;
 int k=0,n=0,m=t.size();
     a[0]=0;
     make_prefix();
     
     
    k=0;
    for(int i=0;i<s.size();i++){
    	while(k && t[k]!=s[i])k=a[k-1];
    	if(t[k]==s[i])k++;
    	if(k==m){
    		k=a[m-1];
    		n++;
    		if(n<1002)
    		x[n]=i-m+1;
    	}
    }
    
    fout<<n<<"\n";
    if(n>1000)n=1000;
for(int i=1;i<=n;i++)fout<<x[i]<<" ";
	
	
}