Pagini recente » Cod sursa (job #820388) | Cod sursa (job #383281) | Cod sursa (job #3281165) | Cod sursa (job #1897541) | Cod sursa (job #3141615)
//#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, MOD1 = 666013, MOD2 = 10027, baza = 73;
#define ll long long
ll hashA1, hashA2;
string a, b;
vector <int> ans;
int main(void)
{
cin >> a >> b;
ll aux1 = 1, aux2 = 1;
for (int i = 0; i < a.size(); ++i) {
hashA1 = (hashA1 * baza + a[i]) % MOD1;
hashA2 = (hashA2 * baza + a[i]) % MOD2;
if (i != 0) aux1 = (aux1 * baza) % MOD1, aux2 = (aux2 * baza) % MOD2;
}
ll p1 = 0, p2 = 0;
for (int i = 0; i < a.size(); ++i) {
p1 = (p1 * baza + b[i]) % MOD1;
p2 = (p2 * baza + b[i]) % MOD2;
}
if (p1 == hashA1 && p2 == hashA2) ans.push_back(1);
for (int i = a.size(); i < b.size(); ++i) {
p1 = ((((p1 - aux1 * b[i - a.size()]) % MOD1) + MOD1) * baza + b[i]) % MOD1;
p2 = ((((p2 - aux2 * b[i - a.size()]) % MOD2) + MOD2) * baza + b[i]) % MOD2;
if (hashA1 == p1 && hashA2 == p2) ans.push_back(i - a.size() + 1);
}
cout << ans.size() << '\n';
for (int i = 0; i < min(static_cast<int>(ans.size()), 1000); ++i) cout << ans[i] << " ";
return 0;
}