Cod sursa(job #478920)

Utilizator barneystinsonBarney barneystinson Data 21 august 2010 04:12:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <vector>
#define NN 2000005
using namespace std;

char P[NN],T[NN];
int pi[NN],cnt;

vector <int> match;

inline void prefix(){
	int k=0,m;
	m=strlen(P+1);
	pi[1]=0;
	for(int q=2;q<=m;q++){
		while(k>0 && (P[k+1] != P[q])) 
			k=pi[k];
		if(P[k+1] == P[q]) 
			k++;
		pi[q]=k;
	}
	
}

inline void kmp(){
	int q=0,m=strlen(P+1),n=strlen(T+1);
	
	for(int i=1;i<=n;i++){
		while(q>0 && P[q+1] != T[i])
			q=pi[q];		
		if(P[q+1] == T[i])
			q++;
		if(q==m){
			cnt++;
			match.push_back(i-q);
		}
	}
	
}

int main(){
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(P+1);
	gets(T+1);
	
	prefix();
	kmp();
	
	printf("%d\n",cnt);
	cnt=0;
	for(vector <int> :: iterator it = match.begin(); it != match.end() && cnt<=1000; it++,cnt++){
		printf("%d ",*it+1);
	}
	
	return 0;
}