Pagini recente » Cod sursa (job #934203) | Cod sursa (job #568939) | Cod sursa (job #1521974) | Cod sursa (job #2902265) | Cod sursa (job #3141601)
//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <cstring>
#include <assert.h>
#include <iomanip>
using namespace std;
const string file = "strmatch";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
#define FAST ios_base::sync_with_stdio(0), cin.tie(0),cout.tie(0) ;
const int NMAX = 2e6 + 5, MOD = 666013;
#define ll long long
string a, b;
vector <int> ans;
ll hasa[NMAX], hasb[NMAX];
ll lgpwr(ll a, int b,int m) {
ll p = 1;
while (b) {
if (b & 1) p = (1LL * p * a) % m;
a = (a * a) % m;
b >>= 1;
}
return p;
}
int main(void)
{
ll baza = 27, aux = 1;
cin >> a >> b;
for (int i = 0; i < a.size(); ++i) {
hasa[i] = (hasa[i - 1] + (1LL * aux * (a[i] - 'A' + 1) % MOD)) % MOD;
aux = (1LL * aux * baza) % MOD;
}
baza = 27, aux = 1;
for (int i = 0; i < b.size(); ++i) {
hasb[i] = (hasb[i - 1] + (1LL * aux * (b[i] - 'A' + 1) % MOD)) % MOD;
aux = (1LL * aux * baza) % MOD;
}
for (int i = a.size()-1; i < b.size(); ++i) {
ll aux_baza = lgpwr(baza, i - a.size() + 1, MOD);
ll inv = lgpwr(aux_baza, MOD - 2, MOD), phash;
if (inv < 0) inv += MOD;
phash = (hasb[i] - hasb[i - a.size()] + MOD) % MOD;
phash = (phash * inv) % MOD;
if (phash == hasa[a.size() - 1]) ans.push_back(i - a.size() + 1);
}
cout << ans.size() << '\n';
for (int i = 0; i < min((int)ans.size(), 1000); ++i) cout << ans[i] << " ";
return 0;
}