Cod sursa(job #627188)

Utilizator razvan2006razvan brezulianu razvan2006 Data 29 octombrie 2011 11:58:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000002
#define MMAX 1001

long i, j, n, L[NMAX], k, nrsol, sol[MMAX];
char P[NMAX], T[NMAX];

int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	
	scanf("%s", P + 1);
	scanf("%s", T + 1);
	long np = strlen(P + 1);
	long nt = strlen(T + 1);
	
	L[1] = 0;
	for(i = 2; i <= np; i++)
	{
		k = L[i - 1];
		while(k > 0 && P[k + 1] != P[i])
			k = L[k];
		if(P[k + 1] == P[i])
			k++;
		L[i] = k;
	}
	
	k = 0;
	for(i = 1; i <= nt; i++)
	{
		while(k > 0 && P[k + 1] != T[i])
			k = L[k];
		if(P[k + 1] == T[i])
			k++;
		if(k == np)
		{
			nrsol++;
			if(nrsol <= 1000)
				sol[nrsol] = i - k;
				
			k = L[k];
		}
	}
	
	printf("%ld\n", nrsol);	
	for(i = 1; i <= nrsol && i <= 1000; i++)
		printf("%ld ", sol[i]);
	
	printf("\n");
			
	return 0;
}