Cod sursa(job #395250)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 12 februarie 2010 17:23:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <cstring>

#define NMAX 2000100

using namespace std;

char A[NMAX], B[NMAX];
int N, M, Pi[NMAX], nrPot, Pot[NMAX];

void Citeste(void)
{
	ifstream fin("strmatch.in");
	
	int i;
	
	fin.getline(A, NMAX);
	fin.getline(B, NMAX);
	
	N = strlen(A);
	M = strlen(B);	
	
	for (i = N; i ; i--)
		A[i] = A[i-1];
	A[0] = ' ';
	
	for (i = M; i ; i--)
		B[i] = B[i - 1];
	B[0] = ' ';
	
	fin.close();
}

void KMP(void)
{
	int i, k = 0;
	
	for (i = 2; i <= N; i++)
	{
		while ( k > 0 && A[k + 1] != A[i] )
			k = Pi[k];
		if (A[k + 1] == A[i])
			k++;
		
		Pi[i] = k;
	}
	
	k = 0;
	
	for (i = 1; i <= M; i++)
	{
		while ( k > 0 && A[k + 1] != B[i])
			k = Pi[k];
		if (A[k + 1] == B[i])
			k++;
		
		if (k == N)
			Pot[++nrPot] = i - N;
	}
}

void Afisare(void)
{
	ofstream fout("strmatch.out");

	int i;
	
	fout <<nrPot <<'\n';
	for (i = 1; i <= nrPot; i++)
		fout <<Pot[i] <<' ';
	
	fout.close();
}

int main()
{
	Citeste();
	
	KMP();
	
	Afisare();
	
	return 0;
}