Pagini recente » Cod sursa (job #19528) | Cod sursa (job #208802) | Cod sursa (job #160157) | Cod sursa (job #2441626) | Cod sursa (job #1313312)
#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;
}