Cod sursa(job #248534)

Utilizator vlad.maneaVlad Manea vlad.manea Data 26 ianuarie 2009 00:04:40
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <string.h>
#define nmax 2000002

char pattern[nmax], text[nmax];
int i, k, lp, lt, L[nmax], matches[nmax];

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

	scanf("%s\n%s", pattern+1, text+1);

	for (text[0] = pattern[0] = ' ', i = 2, lp = strlen(pattern); i <= lp; ++i)
	{	
		k = L[i-1];
		while (k > 0 && pattern[k+1] != pattern[i]) k = L[k];
		if (pattern[k+1] == pattern[i]) k++;
		L[i] = k;
	}

	for (k = 0, i = 1, lt = strlen(text); i <= lt; ++i)
	{
		while (k > 0 && pattern[k+1] != text[i]) k = L[k];
		if (pattern[k+1] == text[i]) k++;
		if (k == lp-1)
		{
			matches[++matches[0]] = i-k;
			k = L[k];

			if (matches[0] >= 1000) break;
		}
	}

	printf("%d\n", matches[0]);
	for (i = 1; i < matches[0]; printf("%d ", matches[i]), ++i);
	printf("%d\n", matches[i]);
}