Pagini recente » Cod sursa (job #1580057) | Cod sursa (job #1463326) | Cod sursa (job #1141232) | Cod sursa (job #2839226) | Cod sursa (job #1313318)
#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;
}
int n = (int)matches.size();
printf("%d\n", n);
n = max(n, 1000);
for (int i = 0; i < n; i++) {
printf("%d ", matches[i]);
}
return 0;
}