Cod sursa(job #608966)

Utilizator ioana454Ioana S ioana454 Data 18 august 2011 21:09:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>


int apps[1000];
int n,m,nSize;
char text[2000000];
char pattern[2000000];
int	fail[2000000];

int SetFailFunction(char *p, int m, int *fail)
{
	int i;
	int k;

	fail[0] = -1;
	for(i=1;i<m;i++)
	{
		k = fail[i-1];
		while(k != -1 && p[i-1] != p[k])
		{
			k = fail[k];
		}
		fail[i] = k+1;
	}
	return 0;
}

int KMP(char *s, int n, char *p, int m, int *f, int *apps, int &nSize)
{
	int i=0;
	int j=0;
	while(i<n)
	{
		while(j != -1 && s[i] != p[j])
		{
			j = f[j];
		}
		
		if(j==(m-1))
		{
			if(nSize<1000)
			{
				apps[nSize] = i-m+1;
				nSize++;				
			}
			else
			{
				nSize++;
			}
			i = i-m+1;
		}

		i = i+1;
		j = j+1;
	}
	return 0;
}


int main()
{
	FILE *f,*g;
	int i;
	f = fopen("strmatch.in","r");
	g = fopen("strmatch.out","w");
	
	fscanf(f,"%s %s",pattern,text);

	n=0;
	m=0;

	while(pattern[m] != 0)
	{
		if(pattern[m]>='a')
		{
			pattern[m] ^= 32;
		}
		m++;
	}
	while(text[n] != 0)
	{
		if(text[n]>='a')
		{
			text[n] ^= 32;
		}
		n++;
	}
	SetFailFunction(pattern,m,fail);
	KMP(text,n,pattern,m,fail,apps,nSize);


	fprintf(g,"%d\n",nSize);
	if(nSize>1000)
	{
		nSize = 1000;
	}
	for(i=0;i<nSize;i++)
	{
		fprintf(g,"%d ",apps[i]);
	}
	fclose(f);
	fclose(g);
	return 0;
}