Cod sursa(job #695048)

Utilizator mateiuliIulian mateiuli Data 28 februarie 2012 10:10:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
#define NMAX 2000002
/**
* Algoritmul Knuth-Morris-Pratt (KMP)
* Potrivirea sirurilor
*/
#define MAXR 1000
vector<int> R;		
int nrR;
int Urm[NMAX];
char T[NMAX], P[NMAX];
int N, M;

void citire();
void urmatorul();
void afisare();

int main()
{
	R.reserve(MAXR);
	int x = -1;
	citire();
	urmatorul();
	
	for(int i=0; i<N; i++)
	{
		while(x > 0 && P[x+1] != T[i])
			x = Urm[x];
		if(P[x+1] == T[i])
			x++;	// s-au potrivit
		if(x == M-1) {
			x = Urm[x];
			nrR++;
			R.push_back(i-M+1);
		}
	}
	
	afisare();
}

void urmatorul()
{
	int k = -1;
	Urm[0] = 0;
	for(int x=1; x<M; x++) 
	{
		while(k > 0 && P[k+1] != P[x])
			k = Urm[k];
		if(P[k+1] == P[x])
			k++;
		Urm[x] = k;
	}
}

void citire()
{
	ifstream fin("strmatch.in");
	fin.getline(P, NMAX);
	fin.getline(T, NMAX);
	N = strlen(T);
	M = strlen(P);
	fin.close();
}

void afisare()
{
	ofstream fout("strmatch.out");
	fout<<nrR<<'\n';
	int i=0;
	vector<int> :: iterator it;
	for(it = R.begin(); it != R.end(); it++, i++) {
		if(i >= MAXR && N >= MAXR)
			break;
		fout<<*it<<' ';
	}
	fout.close();
}