Cod sursa(job #733168)

Utilizator pascu_iulianPascu Iulian pascu_iulian Data 11 aprilie 2012 16:10:39
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#define max 2000002
using namespace std;

int main(){
	char N[max],M[max];
	int n,m,pi[max],k;
	int pos[1000],p=0;
	int i,q;
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	fgets(N, sizeof(N), stdin);
	fgets(M, sizeof(M), stdin);
	for (n=0; (N[n] >= 'A' && N[n] <= 'Z') || (N[n] >= 'a' && N[n] <= 'z') 
			|| (N[n] >= '0' && N[n] <= '9'); ++n);
	for (m=0; (M[m] >= 'A' && M[m] <= 'Z') || (M[m] >= 'a' && M[m] <= 'z')
			|| (M[m] >= '0' && M[m] <= '9'); ++m);
	for (i = n; i; --i) N[i] = N[i-1]; N[0] = ' ';
	for (i = m; i; --i) M[i] = M[i-1]; M[0] = ' ';	
	
	for(pi[1]=0, k=0, i=2; i<=n; i++){
		while(k>0 && N[k+1]!=N[i])
			k=pi[k];
		if(N[k+1]==N[i])
			k++;
		pi[i]=k;
	}
	
	for(q=0,i=1;i<=m;i++){
		while(q>0 && N[q+1]!=M[i])
			q=pi[q];
		if(N[q+1]==M[i])
			q++;
		if(q==n){
			if(p<1000) 
				pos[p]=i-n;
			p++;
			q=pi[n];
		}
	}	
		
	
	printf("%d\n",p);
	for(i=0; i<p && i<1000 ; i++)
		printf("%d ",pos[i]);
	return 0;
}