Cod sursa(job #1409250)

Utilizator vladrochianVlad Rochian vladrochian Data 30 martie 2015 14:16:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <cstring>
using namespace std;

const int kMaxL = 2000005;

char A[kMaxL], B[kMaxL];
int M, N, suff[kMaxL];
int match[1005], cnt;

void Read() {
	ifstream fin("strmatch.in");
	fin.getline(A + 1, kMaxL);
	fin.getline(B + 1, kMaxL);
	M = strlen(A + 1);
	N = strlen(B + 1);
}

void MakePrefix() {
	for (int i = 2, q = 0; i <= M; ++i) {
		while (q && A[q + 1] != A[i])
			q = suff[q];
		if (A[q + 1] == A[i])
			++q;
		suff[i] = q;
	}
}

void Search() {
	for (int i = 1, q = 0; i <= N; ++i) {
		while (q && A[q + 1] != B[i])
			q = suff[q];
		if (A[q + 1] == B[i])
			++q;
		if (q == M) {
			if (cnt < 1000)
				match[cnt] = i - M;
			++cnt;
			q = suff[q];
		}
	}
}

void Print() {
	ofstream fout("strmatch.out");
	fout << cnt << "\n";
	for (int i = 0; i < min(cnt, 1000); ++i)
		fout << match[i] << " ";
	fout << "\n";
}

int main() {
	Read();
	MakePrefix();
	Search();
	Print();
	return 0;
}