Pagini recente » Cod sursa (job #3273088) | Cod sursa (job #3184210) | Borderou de evaluare (job #2443313) | Cod sursa (job #3284758) | Cod sursa (job #3277322)
#include <bits/stdc++.h>
#define type int
using namespace std;
const type MOD = 1e9 + 7;
const type SIZE = 2000000;
type powers[SIZE + 1];
type hashes[SIZE + 1];
type base = 512;
void buildRollingHash(string text)
{
type n = text.size();
for(type i = n - 1; i >= 0; i--)
{
hashes[i] = ((1LL * hashes[i + 1] * base) % MOD + text[i]) % MOD;
}
}
void buildPowerVector(string text)
{
type n = text.size();
powers[0] = 1;
for(type i = 1; i <= n; i++)
{
powers[i] = (1LL * powers[i - 1] * base) % MOD;
}
}
type buildHash(string text)
{
type n = text.size();
type hash = 0;
for(type i = n - 1; i >= 0; i--)
{
hash = ((1LL * hash * base) % MOD + text[i]) % MOD;
}
return hash;
}
type retriveSequenceHashFromRollingHash(type left, type right)
{
return ((hashes[left] - (1LL * hashes[right + 1] * powers[right - left + 1]) % MOD) % MOD + MOD) % MOD;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string tbf, tbs;
cin >> tbf >> tbs;
buildRollingHash(tbs);
buildPowerVector(tbs);
int hash = buildHash(tbf);
int cnt = 0;
for(int i = 0; i + tbf.size() - 1 < tbs.size(); i++)
{
if(retriveSequenceHashFromRollingHash(i, i + tbf.size() - 1) == hash)
{
cnt++;
}
}
cout << cnt << "\n";
cnt = 0;
for(int i = 0; i + tbf.size() - 1 < tbs.size(); i++)
{
if(cnt < 1000 && retriveSequenceHashFromRollingHash(i, i + tbf.size() - 1) == hash)
{
cout << i << " ";
cnt++;
}
}
}