Cod sursa(job #303559)

Utilizator hurrycaneBogdan Gaza hurrycane Data 9 aprilie 2009 23:32:28
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<cstring>
#include<cstdio>
#include<vector>
#define CH (*s-'0')

using namespace std;

struct trie{
	int c;
	int nrfii;
	int ord;
	trie *fiu[100];
	trie(){
		c=0;
		ord=0;
		nrfii=0;
		memset(fiu,0,sizeof(fiu));
	}
};

trie *A=new trie;

vector<trie *> V;
vector<trie *> F;
vector<int> L;

char mead[2050000];
char bed[2005000];

int gf(int state,char *s){
if(V[state]->fiu[CH]!=0) return V[state]->fiu[CH]->ord;
	else return 0;
}

void ins(trie *tr,char *s,int k){
	if(*s=='\n'){
		tr->c++;
		tr->ord=k;
		V.push_back(tr);
		return ;
	}
	if(tr->fiu[CH]==0){
		tr->fiu[CH]=new trie;
		tr->nrfii++;
		if(tr->ord==0) tr->ord=k;
		V.push_back(tr);
	}
	ins(tr->fiu[CH],s+1,k+1);
}



int main(){
	int i,state,st,nrc=0,last=0,length;

	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	fgets(mead,2050000,stdin);
	fgets(bed,205000,stdin);

	ins(A,mead,0);

	int len=strlen(mead)-1;
	length=strlen(bed)-1;
	
	F.push_back(V[0]);
	F.push_back(V[0]);

	for(i=2;i<=len;i++){
		state=F[i-1]->ord;
		last=gf(state,mead+i-1);
		F.push_back(V[last]);
	}

	state=0;
	int gasit=0;
	for(i=0;i<length;i++){
		if(state==len){
			state=F[len]->ord;
		}
		state=gf(state,bed+i);
		if(state==0) {
			if(gasit==1){
				i--;
				state=0;
				gasit=2;
			}
			if(gasit==2){
				i++;
				state=0;
				gasit=0;
			}
			state=F[state]->ord;
		}else{
			gasit=1;
		}

		if(state==len){
			L.push_back(i-len);
			nrc++;
		}

	}
	printf("%d\n",nrc);
	for(int i=0;i<L.size();i++){
		printf("%d ",L[i]+1);
	}
	return 0;
}