Cod sursa(job #611033)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 30 august 2011 14:49:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<cstdio>
#include<vector>
#include<cstring>
#include<ctype.h>
#define Nmax 2000010

using namespace std;

char a[Nmax],b[Nmax];
int N,M,p[Nmax],nr;
vector <int> pot;

void prefix(){
	
	int k=-1;
	p[0]=-1;
	for(int i=1;i<N;++i){
		//   cautam ultimul prefix gasit anterior, pentru care
		//urmatoarea litera dupa el este identica cu a[i]
		while(k>-1 && a[k+1] != a[i])
			k=p[k];
		
		//   daca literele sunt egale inseamna ca exista 
		//un prefix egal cu sufixul de aceeasi lungime (k+1)
		if(a[k+1] == a[i])
			k++;
		
		//   pentru fiecare pozitie de la 1 la N retinem lungimea
		//celui mai lung prefix egal cu sufixul
		p[i]=k;
	}
	
}

void kmp(){
	
	int q=-1;
	for(int i=0;i<M;++i){
		//   ca la prefix, cautam ultima stare valabila dupa
		//concatenarea ultimei liter
		while(q>-1 && a[q+1]!=b[i])
			q=p[q];
		
		//   daca literele se potrivesc adaugam litera la
		//starea actuala
		if(a[q+1]==b[i])
			q++;
		
		//   daca am gasit un sir de lungime N ce
		//verifica automatul -> am gasit o potrivire
		if(q+1==N)
			if(++nr <=1000)
			pot.push_back(i-N+1);
	}
	
}
int main(){
	
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);

	fgets(a,Nmax,stdin);
	fgets(b,Nmax,stdin);
	
	if(!isalpha(a[strlen(a)-1]))
			a[strlen(a)-1]='\0';
	N=strlen(a);
	if(!isalpha(b[strlen(b)-1]))
			b[strlen(b)-1]='\0';
	M=strlen(b);
	
	prefix();
	kmp();
	printf("%d\n",nr);
	for(vector<int>::iterator it=pot.begin();it!=pot.end();++it)
		printf("%d ",*it);
return 0;
}