Pagini recente » Cod sursa (job #2584636) | Cod sursa (job #1386450) | Cod sursa (job #3285465) | Cod sursa (job #3293580) | Cod sursa (job #3293577)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int baza = 200, MOD = 1e9 + 7;
int power[1000001];
int h[1000001], hb;
string a, b;
void precompute()
{
power[0] = 1;
for (int i = 1; i <= 1000000; i++)
power[i] = (1LL * power[i - 1] * baza) % MOD;
h[0] = a[0];
for (int i = 1; i < a.size(); i++)
h[i] = (a[i] + 1LL * h[i - 1] * baza) % MOD;
hb = b[0];
for (int i = 1; i < b.size(); i++)
hb = (b[i] + 1LL * hb * baza) % MOD;
}
long long get_hash(int l, int r)
{
return (h[r] - 1LL * h[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
}
int main()
{
fin >> a >> b;
swap(a, b);
precompute();
vector <int> poz;
int cnt = 0;
for (int i = 0; i <= a.size() - b.size(); i++)
if (get_hash(i, i + b.size() - 1) == hb)
{
cnt++;
poz.push_back(i);
}
fout << cnt << '\n';
for (auto nr : poz)
fout << nr << " ";
return 0;
}