Pagini recente » Cod sursa (job #2308749) | Cod sursa (job #1135278) | Cod sursa (job #2890945) | Cod sursa (job #1856254) | Cod sursa (job #1769568)
#include <bits/stdc++.h>
using namespace std;
class RollingHash{
private:
int hashValue = 0;
int size = 0;
int basePowSize = 0;
int base = 0;
int mod = 0;
int lgPowerRaise(int x,int y, int mod);
public:
RollingHash(int _base, int _mod, int _size);
int getHash();
void appendHash(char c);
void skipHash(char c);
};
int RollingHash::lgPowerRaise(int x, int y, int mod)
{
long long x1 = x,x2 = 1;
if(y == 0)
return 1;
if(y == 1)
return x % mod;
while (y)
if (y & 1) {
y ^= 1;
x2 = (x1 * x2) % mod;
}
else {
y >>= 1;
x1 = (x1 * x1) % mod;
}
return (x1 % mod + mod ) % mod;
}
RollingHash::RollingHash(int _base, int _mod, int _size)
{
hashValue = 0;
base = _base;
mod = _mod;
size = _size;
basePowSize = lgPowerRaise(base, size, mod);
}
int RollingHash::getHash()
{
return hashValue;
}
void RollingHash::appendHash(char c)
{
hashValue = (hashValue * base + c) % mod;
hashValue = (hashValue%mod + mod) % mod;
}
void RollingHash::skipHash(char c)
{
hashValue = (hashValue - basePowSize * c) % mod;
hashValue = (hashValue%mod + mod)%mod;
}
string A,B;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin >> A >> B;
RollingHash hashA(256, 666013, A.size() - 1);
RollingHash hashAA(256, 100003, A.size() - 1);
RollingHash hashB(256, 666013, A.size() - 1);
RollingHash hashBB(256, 100003, A.size() - 1);
for (auto it : A) {
hashA.appendHash(it);
hashAA.appendHash(it);
}
for (int i = 0; i < A.size() - 1; ++i) {
hashB.appendHash(B[i]);
hashBB.appendHash(B[i]);
}
vector<int> answer;
int total = 0;
for(int i = A.size() - 1; i < B.size(); ++i)
{
hashB.appendHash(B[i]);
hashBB.appendHash(B[i]);
if (hashA.getHash() == hashB.getHash() &&
hashAA.getHash() == hashBB.getHash()) {
++total;
if(total <= 1000)
answer.push_back(i - A.size() + 1);
}
hashB.skipHash(B[i - A.size() + 1]);
hashBB.skipHash(B[i - A.size() + 1]);
}
cout << total << "\n";
for(auto it : answer)
cout << it << " ";
return 0;
}