Cod sursa(job #2088181)

Utilizator IulianBobocBoboc Iulian IulianBoboc Data 14 decembrie 2017 20:30:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#include<cstring>
using namespace std;
#define maxLength 2000001
#define threshold 1000
#define max(a,b) (a>b ? a : b)

int i, j, pi[maxLength];
char A[maxLength], B[maxLength];

void computePiFunction(char pattern[]) {
	int k, patternLength = strlen(pattern);

	pi[0] = -1;
	k = -1;
	for (i = 1; i < patternLength; ++i) {
		while (k > -1 && pattern[k + 1] != pattern[i]) {
			k = pi[k];
		}
		if (pattern[k + 1] == pattern[i]) {
			k = k + 1;
		}
		pi[i] = k;
	}
}

int main() {
	ifstream inFile("strmatch.in");
	ofstream outFile("strmatch.out");

	inFile >> A >> B;

	computePiFunction(A);
	int lengthA = strlen(A), lengthB = strlen(B);
	int k = -1, positions = 0, matches[1000];

	for (i = 0; i < lengthB; ++i) {
		while (k > -1 && A[k + 1] != B[i]) {
			k = pi[k];
		}
		if (A[k + 1] == B[i]) {
			k = k + 1;
		}
		if (k == lengthA - 1) {
			if (positions < threshold) {
				positions++;
				matches[positions - 1] = i - k;
			}
		}
	}
	outFile << positions << "\n";
	for (i = 0; i < positions; i++) {
		outFile << matches[i] << " ";
	}
	inFile.close();
	outFile.close();
	return 0;
}