Cod sursa(job #903938)

Utilizator radustn92Radu Stancu radustn92 Data 3 martie 2013 14:30:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <cstring>
#define NMAX 1001
#define LGMAX 2000005
#define LMAX 4000005
using namespace std;
char A[LMAX];
int n, m, pi[LMAX], res[NMAX], ans;

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(A, LGMAX, stdin);
	n = strlen(A) - 1; m = n;
	A[m] = '*';
	fgets(A + m + 1, LGMAX, stdin);
	m = strlen(A) - 1;
	
	int i, q = 0;
	for (i = 2; i <= m; i++)
	{
		while (q && A[q] != A[i - 1])
			q = pi[q];
		
		if (A[q] == A[i - 1])
			q++;
		
		if (q == n)
		{
			if (++ans < NMAX)
				res[ans] = i - 2 * n - 1;
			q = pi[q];
		}
		
		pi[i] = q;
	}
	
	printf("%d\n",ans);
	for (i = 1; i <= ans && i < NMAX; i++)
		printf("%d ",res[i]);
	printf("\n");
	return 0;
}