Cod sursa(job #395244)

Utilizator ErgoVicol Sergiu Constantin Ergo Data 12 februarie 2010 17:00:19
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <cstring>

#define NMAX 2000100

using namespace std;

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

void Citeste(void)
{
	ifstream fin("strmatch.in");
	
	fin.getline(A, NMAX);
	fin.getline(B, NMAX);
	
	N = strlen(A);
	M = strlen(B);	
	
	A[N] = '*';
	
	fin.close();
}

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

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

	int i;
	
	for (i = 0; i < M; i++)
		if (Pi[i] == N - 1)
			nrPot++;
		
	fout <<nrPot <<'\n';
	
	for (i = 0; i < M; i++)
		if (Pi[i] == N - 1)
			fout <<i - N + 1 <<' ';
		
	
	fout.close();
}

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