Pagini recente » Cod sursa (job #517457) | Cod sursa (job #3188611) | Cod sursa (job #828341) | Cod sursa (job #2231905) | Cod sursa (job #1800388)
#include <cstdio>
#include <cstring>
#include <functional>
#include <vector>
using namespace std;
const int lmax = 2000005;
const int mod1 = 100007;
const int mod2 = 100021;
char A[lmax], B[lmax];
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 + (put.first * A[i])) % mod1;
kA.second = (kA.second + (put.second * A[i])) % mod2;
ksecv.first = (ksecv.first + (put.first * B[i])) % mod1;
ksecv.second = (ksecv.second + (put.second * B[i])) % mod2;
if(i > 0) {
put.first = put.first * 73 % mod1;
put.second = put.second * 73 % 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 = ((ksecv.first - (B[i - n] * put.first) % mod1 + mod1) * 73 + B[i]) % mod1;
ksecv.second = ((ksecv.second - (B[i - n] * put.second) % mod2 + mod2) * 73 + B[i]) % mod2;
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;
}