Cod sursa(job #574448)

Utilizator Robert29FMI Tilica Robert Robert29 Data 7 aprilie 2011 10:49:15
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<stdio.h>
#include<string.h>
#define dim 2000001
using namespace std;
FILE*f=fopen("strmatch.in","r");
FILE*g=fopen("strmatch.out","w");
char x,m[dim],M[dim],i,y,v[1001],nr;
int p[2000001];
void prep(char m[],int x){
	int k=0;
	p[1]=0;
	
	for(int i=2;i<=x;++i){
		while(k>0&&m[k+1]!=m[i])
			k=p[k];
		if(m[k+1]==m[i])
			++k;
		p[i]=k;
	}
}
void KMP(char M[],int x,int y){
	int k=0;
	for(int i=1;i<=y;++i){
		while(k>0&&m[k+1]!=M[i])
			k=p[k];
		if(m[k+1]==M[i])
			++k;
		if(k==x)
			if(nr<1000)
				v[++nr]=i-x;
			else ++nr;
	}
	
}
inline int min(int a,int b){
	if(a<b)
		return a;
	else return b;
}
int main() {
	fscanf(f,"%s",m+1);
	fscanf(f,"\n");
	fscanf(f,"%s",M+1);
	
	m[0]='a';
	x=strlen(m)-1;
	m[0]=0;
	prep(m,x);
	
	
	M[0]='a';
	y=strlen(M)-1;
	M[0]=0;
	KMP(M,x,y);
	
	fprintf(g,"%d\n",nr);
	nr=min(nr,1000);
	
	for(i=1;i<=nr;++i)
		fprintf(g,"%d ",v[i]);
	
	fclose(g);
	fclose(f);
	return 0;
}