Cod sursa(job #354421)

Utilizator capmIonut Vasilescu capm Data 7 octombrie 2009 23:19:40
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;

int phi[2000001];
char a[2000010], b[2000010];
char output[10000], nr[10];

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

	int i, j, k, lena, lenb, cnt;
	fgets(a, 2000010, stdin);
	lena = strlen(a);
	fgets(b, 2000001, stdin);
	lenb = strlen(b);

	k = -1;
	phi[0] = -1;
	for(i = 1; i < lena - 1; ++i)
	{
		while(k != -1 && a[k + 1] != a[i])
		{
			k = phi[k];
		}
		if(a[k + 1] == a[i])
		{
			++k;
		}
		phi[i] = k;
	}

	k = -1;
	cnt = 0;
	for(i = 0; i < lenb - 1; ++i)
	{
		while(k != -1 && a[k + 1] != b[i])
		{
			k = phi[k];
		}
		if(a[k + 1] == b[i])
		{
			++k;
		}
		if(k == lena - 2 && cnt < 1000)
		{
			++cnt;
			sprintf(nr, "%d ", i - lena + 2);
			strcat(output, nr);
			k = phi[k];
		}
	}

	printf("%d\n", cnt);
	fputs(output, stdout);



	return 0;
}