Cod sursa(job #1124116)

Utilizator anaid96Nasue Diana anaid96 Data 26 februarie 2014 11:24:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#include<string.h>

using namespace std;

FILE *in,*out;

//functii
void make_prefix();

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

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

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);
	
	make_prefix();
	
	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;
			curentPrefix=prefix[curentPrefix];
		}
	}
	
	fprintf(out,"%d\n",answer);
	if(answer<=1000)
	{
		for(int i=1 ; i<=answer ; ++i)
			fprintf(out,"%d ",answers[i]);
	}	
	else
	{
		for(int i=1 ; i<=1000 ; ++i)
			fprintf(out,"%d ",answers[i]);
	}
	fclose(in);
	fclose(out);
	return 0;
}

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