Cod sursa(job #314355)

Utilizator cotofanaCotofana Cristian cotofana Data 11 mai 2009 16:44:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <string.h>
#define dim 2000001

char a[dim], b[dim], match[dim];
int na, nb, phi[dim], ct=0;

void prefix()
{
	int k=0, q;
	phi[1]=0;
	for (q=2; q<=na; q++)
	{
		while (k && a[k+1]!=a[q]) k=phi[k];
		if (a[k+1]==a[q]) k++;
		phi[q]=k;
	}
}

void kmp()
{
	int q=0, i;
	for (i=1; i<=nb; i++)
	{
		while (q && a[q+1]!=b[i]) 
			q=phi[q];
		if (a[q+1]==b[i]) q++;
		if (q==na) match[i-na]=1, ct++;
	}
}

int main()
{
	int i;
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s\n%s\n", a+1, b+1);
	na=strlen(a+1);
	nb=strlen(b+1);
	prefix();
	kmp();
	printf("%d\n", ct);
	ct=0;
	for (i=0; i<nb && ct<1000; i++)
		if (match[i])
		{
			printf("%d ", i);
			ct++;
		}
	printf("\n");
	return 0;
}