Cod sursa(job #159946)

Utilizator robbyRobertino robert robby Data 14 martie 2008 15:52:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>
#include <string.h>
#define lmax 2000005
char s[lmax],w[lmax];
int n,m,nr,a[lmax/5],t[lmax];
void prep();

FILE *f,*g;
int main()
{
	int i,j;
	f=fopen("strmatch.in","rt");
	g=fopen("strmatch.out","wt");
	fgets(w, lmax, f);
	fgets(s, lmax, f);


	s[strlen(s)-1] = 0;
	w[strlen(w)-1] = 0;

	n=strlen(s);
	m=strlen(w);
	prep();
	i=0;j=0;
	while (i+j<n)
		{
			if (s[i+j]==w[j])
				j++;
			 else
			 {
				i+=j-t[j];
				if (j > 0)
					j = t[j];
			 }

			if (j==m)
				a[++nr]=i;
		}

	fprintf(g, "%d\n", nr);

	for (i = 0; i < nr; i++)
		fprintf(g, "%d ", a[i+1]);

	fclose(f);
	fclose(g);
	return 0;
}


void prep()
{
	int i,j;
	t[0]=-1;
	t[1]=0;
	i=2;
	while (i<=m)
		{
			j=t[i-1];
			while (w[j] != w[i-1] && j != -1)
				j = t[j];

			t[i++] = j + 1;

			j=t[j];
		}
}