Pagini recente » Cod sursa (job #2001327) | Cod sursa (job #3197151) | Cod sursa (job #523735) | Cod sursa (job #981104) | Cod sursa (job #1174124)
#include <vector>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;
#define ONLINE_JUDGE
#define MOD1 666013
#define MOD2 666019
#define base 73
#define pb push_back
#define ENTER fprintf(output, "\n");
#define OKK fprintf(output, "ok!\n");
#define all(V) V.begin(), V.end()
#define allr(V) V.rbegin(), V.rend()
#define LL long long
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
LL hashA1, hashA2, hashB1, hashB2;
string A, B;
LL fact1 = 1, fact2 = 1;
vi ans;
int main() {
#ifdef ONLINE_JUDGE
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
#else
freopen("input.txt", "r", stdin);
#endif
int lgA, lgB, i;
cin >> A >> B;
lgA = A.length();
lgB = B.length();
if (lgA > lgB) {
cout << 0;
return 0;
}
hashA1 = hashA2 = A[0];
hashB1 = hashB2 = B[0];
for (i = 1; i < lgA; ++i, fact1 %= MOD1, fact2 %= MOD2) {
hashA1 = hashA1 * base + A[i]; hashA1 %= MOD1;
hashA2 = hashA2 * base + A[i]; hashA2 %= MOD2;
hashB1 = hashB1 * base + B[i]; hashB1 %= MOD1;
hashB2 = hashB2 * base + B[i]; hashB2 %= MOD2;
fact1 *= base;
fact2 *= base;
}
if (hashA1 == hashB1 && hashA2 == hashB2) {
ans.pb(i - lgA);
//cout << "okk\n";
}
//cout << A << '\n' << B;
for (i = lgA; i < lgB; ++i) {
hashB1 = ((hashB1 + MOD1 - (B[i - lgA] * fact1)) % MOD1) * base + B[i];
hashB2 = ((hashB2 + MOD2 - (B[i - lgA] * fact2)) % MOD2) * base + B[i];
if (hashA1 == hashB1 && hashA2 == hashB2) {
ans.pb(i - lgA + 1);
}
}
cout << ans.size() << '\n';
for (auto x: ans) {
cout << x << ' ';
}
return 0;
}