Cod sursa(job #673889)

Utilizator luckyme91wiz kid luckyme91 Data 5 februarie 2012 03:53:48
Problema Potrivirea sirurilor Scor 12
Compilator c Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <stdlib.h>
#define min(a, b) ((a < b) ? a : b)
#define NMAX 2000000
char s1[NMAX], s2[NMAX];
int table[NMAX], where[1000];

int main () {

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

//char s1[NMAX], s2[NMAX];
//int table[NMAX], where[1000];
gets(s1);
gets(s2);

table[0] = -1;
int k = -1;

int i;
for (i = 1; s1[i + 1] != '\0'; i++)
{
	while (k > -1 && s1[k + 1] != s1[i])
		k = table[k];
	if (s1[i] == s1[k + 1])
		k++;
	table[i] = k;
}
int j = -1, count = 0;
for (i = 0; s2[i] != '\0'; i++)
{
	while (j > -1 && s1[j + 1] != s2[i])
		j = table[j];
	if (s2[i] == s1[j + 1])
		j++;
	if (i == 474)
		printf("%d\n", j);	
	if (s1[j + 1] == '\0')
	{
		count ++;
		//j = table[j];
		if (count <= 1000)
			where[count - 1] = i - j;
		j = table[j];
	}
}
printf ("%d\n", count);
for (i = 0; i < min(count, 1000); i++)
	printf ("%d ", where[i]);
return 0;
}