Cod sursa(job #143814)

Utilizator coderninuHasna Robert coderninu Data 26 februarie 2008 21:28:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>
#include <string.h>
#define Nmax 200001

char P[Nmax], S[Nmax];
int c[1005], pi[Nmax], i, j, n, m;

int main()
{
	freopen("strmatch.in", "r", stdin);
	scanf("%s\n%s", &P, &S);
	fclose(stdin);

	for (i=0, pi[0]=-1, j=-1, m=strlen(P); i<m; i++, pi[i]=++j)
		while (j>=0 && P[i]!=P[j])
			j=pi[j];
	for (i=0, j=0, n=strlen(S); i<=n; i++)
	{
		while (P[j] !=S[i] && j) j=pi[j];
		if (P[j]==S[i]) j++;
		if (j==m) 
		{
			c[++c[0]]=i-m+1;
			if (c[0]==1000) break;
			j=pi[j];
		}
	}
	freopen("strmatch.out", "w", stdout);
	printf("%d\n", c[0]);
        for (i=1; i<=c[0]; i++) printf("%d ", c[i]);
        return 0;
}