Cod sursa(job #1839513)

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

#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();
	for (int i = 0; i < N; ++ i) {
		while (j != 0 && A[j] != B[i]) {
			j = temp_array[j - 1];
		}

		if (B[i] == A[j]) {
			++ j;
		}

		if (j == A.size()) {
			if (matches.size() <= 1000)
			matches.push_back(i - j + 1);
			j = temp_array[j - 1];
		}
	}

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