Cod sursa(job #162310)

Utilizator anoukAnca Dumitrache anouk Data 19 martie 2008 21:21:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <cstring>
#define DIM 2000002
using namespace std;

char A[DIM], B[DIM];
int N, M, pi[DIM], poz[1024], sol;

void Prefix()
{
	int k = 0;
	for (int i = 2; i <= M; i++)
	{
		while (k > 0 && A[k + 1] != A[i]) k = pi[k];
		if (A[k + 1] == A[i]) k++;
		pi[i] = k;
	}
}

void KMP()
{
	int k = 0;
	for (int i = 1; i <= N; i++)
	{
		while (k > 0 && A[k + 1] != B[i]) k = pi[k];
		if (A[k + 1] == B[i]) k++;
		if (k == M)
		{
			sol++;
			poz[sol] = i - M;
			k = pi[k];
		}
	}
}

int main()
{
	FILE *fin = fopen("strmatch.in", "r");
	FILE *fout = fopen("strmatch.out", "w");
	
	fscanf(fin, "%s%s", &A, &B);
	M = strlen(A);
	N = strlen(B);
	for (int i = M; i > 0; i--) A[i] = A[i - 1];
	for (int j = N; j > 0; j--) B[j] = B[j - 1];
	Prefix();
	KMP();
	fprintf(fout, "%d\n", sol);
	for (int i = 1; i <= sol; i++)
		fprintf(fout, "%d ", poz[i]);

	return 0;
}