Cod sursa(job #673882)

Utilizator luckyme91wiz kid luckyme91 Data 5 februarie 2012 02:02:02
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 2000000
int main () {

freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);

char s1[NMAX], s2[NMAX], table[NMAX], where[NMAX];
gets(s1);
gets(s2);
table[0] = 0;
table[1] = 0;
char k = 0;
int i, p = 0;
for (i = 2; s1[i + 1] != '\0'; i++)
{
	while (k > 0 && s1[k] != s1[i])
		k = table[k - 1];
	if (s1[i] == s1[k])
		k++;
	table[i] = k - 1;
}
int j = 0, count = 0, poz = 0;
for (i = 0; s2[i + 1] != '\0'; i++)
{
	if (s2[i] == s1[j])
		j++;
	else
	{
		poz = i + 1 - table[j];
		if (j - 1 > 1)
			j = table[j - 1] + 1;
		else
			j = 0;
	}
	if (s1[j] == '\0')
	{
		count ++;
		j = 0;
		where[p++] = poz;
		i = poz;
		poz = i + 1;
	}
}
printf ("%d\n", count);
for (i = 0; i < p; i++)
	printf ("%d ", where[i]);
return 0;
}