Cod sursa(job #1167370)

Utilizator dimitriepirghiePirghie Dimitrie dimitriepirghie Data 4 aprilie 2014 21:09:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<string>
using namespace std;
int nrOfMatches = 0, matches[1005],kmpNext[2000000];
ifstream inputStream("strmatch.in");
ofstream outputStream("strmatch.out");
void preKmp(char *x, int m, int kmpNext[]) {
	int i, j;

	i = 0;
	j = kmpNext[0] = -1;
	while (i < m) {
		while (j > -1 && x[i] != x[j])
			j = kmpNext[j];
		i++;
		j++;
		if (x[i] == x[j])
			kmpNext[i] = kmpNext[j];
		else
			kmpNext[i] = j;
	}
}


void KMP(char *x, int m, char *y, int n) {
	int i, j;

	/* Preprocessing */
	preKmp(x, m, kmpNext);

	/* Searching */
	i = j = 0;
	while (j < n) {
		while (i > -1 && x[i] != y[j])
			i = kmpNext[i];
		i++;
		j++;
		if (i >= m) {
			matches[nrOfMatches] = j - i;
			nrOfMatches++;
			i = kmpNext[i];
		}
	}
}
int main()
{
	string pattern, subject;
	getline(inputStream, pattern);
	getline(inputStream, subject);
	char* patt = const_cast<char*>(pattern.c_str());
	char* subj = const_cast<char*>(subject.c_str());

	KMP(patt, pattern.size(), subj, subject.size());
	outputStream << nrOfMatches << std::endl;
	for (int i = 0; i < nrOfMatches; i++)
		outputStream << matches[i] << " ";
	return 0;
}