Cod sursa(job #1313312)

Utilizator whoasdas dasdas who Data 10 ianuarie 2015 15:48:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#define IA_PROB "strmatch"

#include <cstdio>
#include <cstring>

#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <algorithm>

using namespace std;




int main()
{
	freopen(IA_PROB".in", "r", stdin);
	freopen(IA_PROB".out", "w", stdout);
	const int NMAX = 2000002;
	char *P = new char[NMAX], *p;
	char *T = new char[NMAX], *t;

	const int prime = 101, mod = 100021;

	long long int hP = 0, hT = 0;
	int prime2lenP = 1;
	int lenP = 0;
	vector<int> matches;

	scanf("%s %s", P, T);

	for (p = P; *p; p++, lenP++) {
		hP = (hP * prime + *p) % mod;
		if (lenP)	/* we actually want prime^(lenP-1) */
			prime2lenP = prime2lenP * prime % mod;
	}

	for (t = T; *t && t - T < lenP; t++) {
		hT = (hT * prime + *t) % mod;
	}
	if (t - T < lenP) {
		printf("0\n");
		return 0;
	}

	for (; *(t - 1); t++) {
		if (hT == hP && memcmp(P, t - lenP, lenP) == 0) {
			matches.push_back(t - T - lenP);
		}
		hT = ((mod + hT - prime2lenP * *(t - lenP) % mod) * prime + *t) % mod;
	}

	printf("%d\n", matches.size());
	int i = 0;
	for (vector<int>::iterator it = matches.begin(); it != matches.end() && i < 1000; ++it, ++i) {
		printf("%d ", *it);
	}

	return 0;
}