Cod sursa(job #2088190)

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

int i, j, pi[maxLength], matches[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;

	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) {
			matches[positions++] = i - k;
		}
	}
	outFile << positions << "\n";
	for (i = 0; i < min(threshold, positions); i++) {
		outFile << matches[i] << " ";
	}
	inFile.close();
	outFile.close();
	return 0;
}