Cod sursa(job #1135534)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 7 martie 2014 23:09:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<string>

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



main(){
//	ifstream fin("strmatch.in");
//	ofstream fout("strmatch.out");
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","r",stdout);
//	scanF("%d %d",t,s);
	fgets(t, sizeof(t), stdin);
    fgets(s, sizeof(s), stdin);
//	fin>>t>>s;
	int m=0,m1=0,M=0;
	for (; (t[M] >= 'A' && t[M] <= 'Z') || (t[M] >= 'a' && t[M] <= 'z')|| (t[M] >= '0' && t[M] <= '9'); ++M);
	m=M;M=0;
	for (; (s[M] >= 'A' && s[M] <= 'Z') || (s[M] >= 'a' && s[M] <= 'z')|| (s[M] >= '0' && s[M] <= '9'); ++M);
	m1=M;

   int k=0,n=0;
    a[0]=0;
    
    
    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;
    }
    k=0;
    for(int i=0;i<m1;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";
   printf("%d\n",n);
    if(n>1000)n=1000;
for(int i=1;i<=n;i++)//fout<<x[i]<<" "; 
printf("%d ",x[i]);
	
	
	
}