Pagini recente » Cod sursa (job #1979656) | Cod sursa (job #162291) | Cod sursa (job #1158949) | Cod sursa (job #228438) | Cod sursa (job #1800380)
#include <cstdio>
#include <cstring>
#include <functional>
#include <vector>
using namespace std;
const int lmax = 2000005;
const int miliard = 1000000000;
const int mod1 = miliard + 3;
const int mod2 = miliard + 7;
char A[lmax], B[lmax];
inline int getn(char c) {
return c - 'A';
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(A);
gets(B);
int n = strlen(A), N = strlen(B);
pair<int, int> kA = make_pair(0, 0), put = make_pair(1, 1), ksecv = make_pair(0, 0);
for(int i = n - 1; i >= 0; -- i) {
kA.first = (kA.first + (1LL * put.first * getn(A[i]) % mod1)) % mod1;
kA.second = (kA.second + (1LL * put.second * getn(A[i]) % mod2)) % mod2;
ksecv.first = (ksecv.first + (1LL * put.first * getn(B[i]) % mod1)) % mod1;
ksecv.second = (ksecv.second + (1LL * put.second * getn(B[i]) % mod2)) % mod2;
if(i > 0) {
put.first = put.first * 26LL % mod1;
put.second = put.second * 26LL % mod2;
}
}
vector<int> positions;
if(kA.first == ksecv.first and kA.second == ksecv.second)
positions.push_back(0);
for(int i = n; i < N; ++ i) {
ksecv.first = (26LL * (ksecv.first - (1LL * getn(B[i - n]) * put.first) % mod1) % mod1 + getn(B[i]) % mod1) % mod1;
ksecv.second = (26LL * (ksecv.second - (1LL * getn(B[i - n]) * put.second) % mod2) % mod2 + getn(B[i]) % mod2) % mod2;
fprintf(stderr, "%d %d\n", ksecv.first, ksecv.second);
if(ksecv.first == kA.first and ksecv.second == kA.second)
positions.push_back(i - n + 1);
}
printf("%u\n", positions.size());
for(int i = 0; i < min((int)positions.size(), 1000); ++ i)
printf("%d ", positions[i]);
printf("\n");
return 0;
}