Pagini recente » Cod sursa (job #2923804) | Cod sursa (job #1323737) | Cod sursa (job #1393399) | Cod sursa (job #2914931) | Cod sursa (job #1769600)
#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(int c);
void skipHash(int 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 (x2 % 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(int c)
{
hashValue = (hashValue * base + c) % mod;
}
void RollingHash::skipHash(int c)
{
hashValue = (hashValue - basePowSize * c) % mod;
hashValue = (hashValue + mod) % mod;
}
const int Nmax = 2000005;
char A[Nmax],B[Nmax];
int N,M;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",&A,&B);
N = strlen(A);
M = strlen(B);
RollingHash hashA(256, 666013, N - 1);
RollingHash hashAA(256, 100003, N - 1);
RollingHash hashB(256, 666013, N - 1);
RollingHash hashBB(256, 100003, N - 1);
for (int i = 0; i < N; ++i) {
hashA.appendHash(A[i]);
hashAA.appendHash(A[i]);
}
for (int i = 0; i < N - 1; ++i) {
hashB.appendHash(B[i]);
hashBB.appendHash(B[i]);
}
vector<int> answer;
int total = 0;
for(int i = N - 1; i < M; ++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 - N + 1);
}
hashB.skipHash(B[i - N + 1]);
hashBB.skipHash(B[i - N + 1]);
}
cout << total << "\n";
for(auto it : answer)
cout << it << " ";
return 0;
}