Cod sursa(job #1998249)

Utilizator contnouAndrei Pavel contnou Data 7 iulie 2017 01:49:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<string.h>
#define MAXLEN 2000005

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[MAXLEN], B[MAXLEN];
int prefix[MAXLEN], matches[MAXLEN], lMatches;

void buildPrefixArray(int *prefix, char *A) {
	//
	int crt = 0;
	int l = strlen(A);
	prefix[0] = 0;
	for (int i = 1; i < l; i++) {
		int len = prefix[i - 1];
		while (len != 0 && A[len] != A[i]) {
			len = prefix[len - 1];
		}
		if (A[len] == A[i]) prefix[i] = len + 1;
	}
}

void printMatches(int prefix[], char A[], char B[], int matches[], int &lMatches) {
	//
	int crt = 0;
	int lB = strlen(B);
	int lA = strlen(A);
	lMatches = 0;
	int len = 0;
	for (int i = 0; i < lB; i++) {
		//
		while (len != 0 && A[len] != B[i]) {
			len = prefix[len - 1];
		}
		if (A[len] == B[i]) len++;
		if (len == lA) {
			matches[++lMatches] = i - lA + 1;
			len = prefix[len - 1];
		}
	}
}
int main() {
	//
	f >> A;
	f >> B;
	buildPrefixArray(prefix, A);
	printMatches(prefix, A, B, matches, lMatches);
	g << lMatches << endl;
	lMatches = lMatches > 1000 ? 1000 : lMatches;
	for (int i = 1; i <= lMatches; i++)
		g << matches[i] << " ";
	return 0;
}