Cod sursa(job #1131504)

Utilizator anaid96Nasue Diana anaid96 Data 28 februarie 2014 20:39:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 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 strLen,subLen;
int answer,answers[1001];
int prefix[sz];

int main(void)
{
	in=fopen("strmatch.in","rt");
	out=fopen("strmatch.out","wt");
	
	fscanf(in,"%s",sub+1);
	fscanf(in,"%s",str+1);
	
	strLen = strlen(str+1);
	subLen = strlen(sub+1);
	
	make_prefix();
	
	int curentPrefix=0;
	
	for(int i=1 ; i<=strLen ; ++i)
	{
		while(curentPrefix && str[i]!=sub[curentPrefix+1])
			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;
	}
}