Cod sursa(job #903936)

Utilizator radustn92Radu Stancu radustn92 Data 3 martie 2013 14:21:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <string>
#include <iostream>
#define NMAX 1001
#define LMAX 4000005
using namespace std;
string A, B;
int pi[LMAX], res[NMAX], ans;

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	cin >> A >> B;
	A = A + '*' + B;
	
	int i, n = A.length() - B.length() - 1, q = 0;
	for (i = 2; i <= A.length(); 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;
}