Cod sursa(job #2259235)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 13 octombrie 2018 10:44:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MAX 2000005
#define THRESH 1000
using namespace std;

char a[MAX], b[MAX];
int n, m, k, pi[MAX];
vector<int> res;

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

	f >> a + 1 >> b + 1;
	n = strlen(a + 1);
	m = strlen(b + 1);

	k = 0;
	for (int i = 2; i <= n; ++i) {
		while (k && a[i] != a[k + 1])
			k = pi[k];
		if (a[k + 1] == a[i])
			++k;
		pi[i] = k;
	}

	k = 0;
	for (int i = 1; i <= m; ++i) {
		while (k && b[i] != a[k + 1])
			k = pi[k];
		if (b[i] == a[k + 1])
			++k;
		if (k == n) {
			res.push_back(i - n);
			if (res.size() == THRESH)
				break;
		}
	}

	g << res.size() << "\n";
	for (int i = 0; i < res.size(); ++i)
		g << res[i] << " ";
	g << "\n";

	return 0;
}