Cod sursa(job #1310602)

Utilizator whoasdas dasdas who Data 6 ianuarie 2015 23:45:06
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 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;

const int NMAX = 2000002;


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

	const int prime = 101;

	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++) {
		hP = hP * prime + *p;
		prime2lenP *= prime;
		lenP++;
	}
	prime2lenP /= prime; /* we actually want prime^(lenP-1) */

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

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

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

	return 0;
}