Cod sursa(job #1168891)

Utilizator andreey_047Andrei Maxim andreey_047 Data 9 aprilie 2014 20:51:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <cstdio>
#include <cstring>
using namespace std;

char A[2000001],B[2000001];
int total,pi[2000001],m,n,sol[1005];
void Prefix()
{
	int i, q = 0;

	for (i = 2, pi[1] = 0; i <= m; ++i)
	{
		while (q && A[q+1] != A[i])
			q = pi[q];
		if (A[q+1] == A[i])
			++q;
		pi[i] = q;
	}
}
void Solve()
{
	int q = 0;
	for (int i = 1; i <= n; ++i)
	{
		while (q && A[q+1] != B[i])
			q = pi[q];
		if (A[q+1] == B[i])
			++q;
		if (q == m)
		{
			q = pi[m];
			if(total < 1000)
				sol[total] = i-m;
			total++;
		}
	}
}
void Show()
{
	printf("%d\n",total);
	for(int i = 0; i < total; i++)
		printf("%d ",sol[i]);
}
int main(){
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",A+1,B+1);
    m=strlen(A+1);
    n=strlen(B+1);
    Prefix();
    Solve();
    Show();
    return 0;
}