Cod sursa(job #263927)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 20 februarie 2009 22:53:00
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.41 kb
#include<stdio.h>
#include<string.h>
#define infile "strmatch.in"
#define outfile "strmatch.out"
#define lmax (2*1000*1000+10)
#define nrmax 1001
char a[lmax],b[lmax]; //cele doua siruri
int s[nrmax]; //aici salvam potrivirile:P
int urm[lmax]; //vectorul care spune pozitia urmatoare
int n,m; //lungimile celor doua siruri
int nr;

int minim(int a, int b)
	{
	if(a<b) return a; return b;
	}

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=0;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
		if(++nr<nrmax) s[nr]=i-k; //salvam pozitia de inceput
	}
//afisem
printf("%d\n",nr); //numarul de aparitii
for(i=1;i<=minim(nr,nrmax-1);printf("%d ",s[i++])); //pozitiile de start (doar pt primele NRMAX potriviri)

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