Cod sursa(job #1119153)

Utilizator anaid96Nasue Diana anaid96 Data 24 februarie 2014 15:42:02
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<string.h>

using namespace std;

FILE *in,*out;

//functii
void makePrefix();

//constante
const int sz=(int) 2e6+1;

//variabile
char sub[sz];
char str[sz];
int subLen,strLen;
int prefix[sz];
int answers[1001],answer;

int main(void)
{
	in=fopen("strmatch.in","rt");
	out=fopen("strmatch.out","wt");
	
	fscanf(in,"%s",sub+1);
	fscanf(in,"%s",str+1);
		
	subLen=strlen(sub+1);
	strLen=strlen(str+1);
	
	makePrefix();
	
	int curentPrefix = 0;
	
	for(int i=1 ; i<=strLen ; ++i)
	{
		while(curentPrefix && sub[curentPrefix+1]!=str[i])
			curentPrefix=prefix[curentPrefix];
			
		if(sub[curentPrefix+1] == str[i])
			++curentPrefix;
		if(curentPrefix==subLen)
		{	
			if(++answer <= 1000)
				answers[answer]=i-subLen+1;
			
			curentPrefix=prefix[curentPrefix];
		}	
			
	}
	fprintf(out,"%d\n",answer);	
	for(int i=1 ; i<=answer ; ++i)
		fprintf(out,"%d ",answers[i]);
	fclose(in);
	fclose(out);
	return 0;
}	

void makePrefix()
{
	int curentPrefix = 0;
	for(int i=2 ; i<=subLen ; ++i)
	{	
		while(curentPrefix && sub[i]!=sub[curentPrefix+1])
			curentPrefix = prefix[curentPrefix]; 
			
		if(sub[curentPrefix+1] == sub[i])
			++curentPrefix;
		
		prefix[i]=curentPrefix;	
	}
}