Cod sursa(job #1349195)

Utilizator eukristianCristian L. eukristian Data 20 februarie 2015 00:43:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <cstring>
#include <vector>


using namespace std;

#define MAXN 2000002

char a[MAXN];
char b[MAXN];

int N, alen, blen;
int pref[MAXN];
vector<int> matches;

void computePref()
{
	int i, k = 0;
	pref[1] = 0;

	for (i = 2 ; i <= alen ; ++i)
	{
		while (k > 0 && a[k+1] != a[i])
			k = pref[k];
		if (a[k+1] == a[i])
			k++;
		pref[i]=k;
	}
}

void kmp()
{
	int i, k = 0;

	for (i = 1 ; i <= blen ; ++i)
	{
		while (k > 0 && b[i] != a[k + 1])
			k = pref[k];

		if (b[i] == a[k+1])
			k++;

		if (k == alen) // we've got a match
		{
			N++;
			if (N < 1000)
			{
				matches.push_back(i - alen);
			}
		}
	}
}

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

	scanf("%s", a+1);
	scanf("%s", b+1);

	alen = strlen(a + 1);
	blen = strlen(b + 1);

	computePref();
	kmp();

	printf("%d\n", N);

	for (vector<int>::iterator it = matches.begin() ; it != matches.end() ; ++it)
		printf("%d ", *it);
	printf("\n");

	return 0;
}