Cod sursa(job #170794)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 3 aprilie 2008 11:19:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <string.h>
const int n_max = 2000100;
const int s_max = 1009;
char s1[n_max],
     s2[n_max];
int r, sol[s_max], n, m, pi[n_max];
void prefix()
{
	int k = 0;
	for (int i = 2; i <= n; ++ i)
	{
		while (k > 0 && s1[k+1]!= s1[i])
			k = pi[k];
		if (s1[k+1] == s1[i])
			pi[i] = ++k;
	}
}
void kmp()
{
	int k = 0;
	for (int i = 1; i <= m; ++ i)
	{
		while (k > 0 && s1[k+1] != s2[i])
			k = pi[k];
		if (s2[i] == s1[k+1])
			++k;
//		printf("%d ", k);
		if (k == n)
		{
			++r;
			if (sol[0] < 1000)
				sol[++sol[0]] = i-n;
			k= pi[k];
		}
	}
}
		


int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s\n%s\n", s1+1, s2+1);
	n = strlen(s1+1);
	m = strlen(s2+1);
	
	prefix();
	
	kmp();
	printf("%d\n", r);
	for (int i = 1; i <= sol[0]; ++ i)
		printf("%d ", sol[i]);
	return 0;
}