Cod sursa(job #263852)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 20 februarie 2009 21:18:43
Problema Potrivirea sirurilor Scor 38
Compilator c Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#include<string.h>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define lmax 2*1000*1000
#define nmax 500*1000
char a[lmax],b[lmax]; //cele doua siruri
int s[nmax]; //aici salvam potrivirile:P
int urm[lmax]; //vectorul care spune pozitia urmatoare
int n,m; //lungimile celor doua siruri

void urmatorul()
	{
	int i,k=-1;
	for(i=1;i<n;i++)
		{
		while(k>0&&a[i]!=a[k+1]) k=urm[k]; //cat timp nu gasim un sir pe care sa il putem continua
		if(a[i]==a[k+1]) k++; //daca pozitia urmatoare este corecta, o continuam
		urm[i]=k; //salvam lungimea
		}
	}

int main()
{
int i,k=-1;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

fgets(a,lmax,stdin); n=strlen(a)-1; //citim sirul si ii aflam lungimea (stergem caracterul \n)
fgets(b,lmax,stdin); m=strlen(b); //citim sirul si ii aflam lungimea
urmatorul(); //construim vectorul urm[]
//facem cautarea
for(i=1;i<m;i++)
	{
	while(k>0&&a[k+1]!=b[i]) k=urm[k];
	if(b[i]==a[k+1]) k++; //se potriveste, deci inaintam
	if(k==n-1) //inseamna k am gasit o asemanare a lui a in b
		s[++s[0]]=i-k; //salvam pozitia de inceput
	}
//afisem
printf("%d\n",s[0]); //numarul de aparitii
for(i=1;i<=s[0];printf("%d ",s[i++])); //afisem pozitiile de start

fclose(stdin);
fclose(stdout);
return 0;
}