Cod sursa(job #554014)

Utilizator BuRNB Radu BuRN Data 14 martie 2011 14:57:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <cstdio>
#include <string>
using namespace std;

#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define nmax 2000005

char t[nmax], p[nmax];
long l[nmax], n, m, total, sol[1000];

void citire()
{
	freopen(FIN,"r",stdin); 
	scanf("%s %s", p+1, t+1); n = strlen(t+1); m = strlen(p+1);
}

void afisare()
{
	freopen(FOUT,"w",stdout);
	printf("%ld\n", total);
	for(int i=0; i<(total<1000 ? total:1000); i++)
		printf("%ld ", sol[i]);
}

void prefix()
{ 
	int k = 0;
	for (int i=2; i<=m; i++)
	{
		while (k && p[k+1] != p[i])
			k = l[k];
		if (p[k+1] == p[i])
			k++;
		l[i] = k;
	} 
}

void kmp()
{
	int k = 0;
	for (int i=1; i<=n; i++)
	{		
		while (k && p[k+1] != t[i])
			k = l[k];
		if (p[k+1] == t[i])
			k++;

		if (k == m)
		{
			k = l[m];
			if(total < 1000)
				sol[total] = i-m;
			total++;
		}	
	}		   
}


int main()
{	
	citire();
	prefix();
	kmp();
	afisare();
	return 0;
}