Cod sursa(job #627179)

Utilizator razvan2006razvan brezulianu razvan2006 Data 29 octombrie 2011 11:43:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
#include<string.h>

long i, j, n, L[2000001], k, nrsol, sol[1002];
char P[2000001], T[2000001];

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