Cod sursa(job #1839488)

Utilizator cat_a_stropheTina Elisse Pop cat_a_strophe Data 2 ianuarie 2017 22:57:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <string.h>

#define NMAX 2000000
#define MAXSIZE 1000
using namespace std;

vector<int> BuildTempArray(char s[]) {
	int i = 1;
	int j = 0;
	int n = strlen(s);
	vector<int> temp_array;
	temp_array.push_back(0);
	while (i < n) {
		if (s[i] == s[j]) {
			temp_array.push_back(temp_array[j] + 1);
			++ i; ++j;
		} else {
			if (j) {
				j = temp_array[j - 1];
			} else {
				temp_array.push_back(0);
				++ i;
			}
		}
	}

	return temp_array;
}

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	char A[NMAX], B[NMAX];

	scanf("%s", A);
	scanf("%s", B);

	vector<int> temp_array = BuildTempArray(A);

	// for (int i = 0; i < temp_array.size(); ++ i) {
	// 	printf("%d ", temp_array[i]);
	// }

	vector<int> matches;
	
	int j = 0;
	int N = strlen(B);
	bool should_stop = false;
	for (int i = 0; i < N && !should_stop; ++ i) {
		while (j != 0 && A[j] != B[i] && !should_stop) {
			j = temp_array[j - 1];
		}

		if (B[i] == A[j]) {
			++ j;
		}
		if (j == strlen(A)) {
			j = temp_array[j - 1];
			matches.push_back(i - j - 1);
			if (matches.size() == MAXSIZE) {
				should_stop = true;
			} 
		}
	}

	printf("%d\n", (int)matches.size());
	for (int i = 0; i < matches.size(); ++ i) {
		printf("%d ", matches[i]);
	}
	printf("\n");
	return 0;
}