Cod sursa(job #303023)

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

using namespace std;

struct trie{
	int c;
	int nrfii;
	int ord;
	trie *fiu[58];
	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[2000000];
char bed[2000000];

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;
	int state;
	int st;
	int nrc=0;
	int last=0;

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

	fgets(mead,35,stdin);
	ins(A,mead,0);
	int len=strlen(mead)-1;

	F.push_back(V[0]);
	F.push_back(V[0]);

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

	fgets(bed,35,stdin);
	int length=strlen(bed)-1;
	state=0;
	for(i=0;i<length;i++){
		st=gf(state,bed+i);
		if(st==0) {
			if(state==len) {
				L.push_back(last);
				last=i-(F[state]->ord);
				state=F[state]->ord+1;
				nrc++;
			}
			else state=F[state]->ord;
		}else state=st;

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