Cod sursa(job #527328)

Utilizator Light532Light 532 Light532 Data 31 ianuarie 2011 11:10:44
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 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++;
				i = i-m+1;
			}
			else
			{
				return 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)
		m++;
	while(text[n] != 0)
		n++;
	SetFailFunction(pattern,m,fail);
	KMP(text,n,pattern,m,fail,apps,nSize);
	
	fprintf(g,"%d\n",n);
	for(i=0;i<nSize;i++)
	{
		fprintf(g,"%d ",apps[i]);
	}
	fclose(f);
	fclose(g);
	return 0;
}