Pagini recente » Cod sursa (job #854027) | Cod sursa (job #1216500) | Cod sursa (job #297315) | Cod sursa (job #1582436) | Cod sursa (job #1310602)
#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;
}