Cod sursa(job #369957)

Utilizator titusuTitus C titusu Data 29 noiembrie 2009 21:33:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
using namespace std;
#include <cstdio>
#define MAX 2000010
#define nrLitere (26+26+10)
#define nrPrim 100021
char s[MAX], p[MAX];
int ns,np;
FILE * fin= fopen("strmatch.in","r");
FILE * fout=fopen("strmatch.out","w");

void read();
void KMP();
void write();

int main(){
		read();
		KMP();
		write();
		return 0;
	}

void read(){
	ns=np=0;
	fscanf(fin,"%s%s",p,s);
	for( ; s[ns] ; ++ns);
	for( ; p[np] ; ++np);
}

int nrpoz, nrpp, poz[1010];

void KMP(){
	//pregatesc funtia failure
	int T[MAX], pos=2, cnd=0;
	T[0] = -1, T[1] = 0;
	while(pos<=np)
		if(p[pos-1] == p[cnd])
			T[pos]=cnd+1,pos++,cnd++;
		else
			if(cnd>0)
				cnd = T[cnd];
			else
				T[pos++] = 0;
	//KMP
	int m=0,i=0;
	while(m+i<ns)
	{
//		printf("%d %d\n",m,i);
		if(p[i] ==s[m+i]){
			i++;
			if(i==np){
					nrpoz++;
					if(nrpoz<=1000)
						poz[++nrpp] = m;
					m = m+i-T[i];
					if(i>0) i = T[i];
				}
		}
		else{
			m = m+i-T[i];
			if(i>0) i = T[i];
		}
	}
}

void write(){
	fprintf(fout,"%d\n",nrpoz);
	for(int i=1;i<=nrpp;++i)
		fprintf(fout,"%d ",poz[i]);
}