Cod sursa(job #1839511)

Utilizator cat_a_stropheTina Elisse Pop cat_a_strophe Data 2 ianuarie 2017 23:41:05
Problema Potrivirea sirurilor Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <string.h>

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

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int temp_array[NMAX];
int N = 1;
string A, B;

void BuildTempArray() {
	int i = 1;
	int j = 0;
	int n = A.size();

	temp_array[0] = 0;
	while (i < n) {
		if (A[i] == A[j]) {
			temp_array[N ++] = temp_array[i - 1] + 1;
			++j;
		} else {
			if (j) {
				j = temp_array[j - 1];
			} else {
				temp_array[N ++] = 0;
			}
		}
		++ i;
	}
}

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

	in >> A >> B;

	BuildTempArray();

	vector<int> matches;
	
	int j = 0;
	int N = B.size();
	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 == A.size()) {
			matches.push_back(i - j + 1);
			j = temp_array[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;
}