Pagini recente » Cod sursa (job #382446) | Cod sursa (job #2341279) | Cod sursa (job #81043) | Cod sursa (job #2167440) | Cod sursa (job #2284557)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
char p[2000005], t[2000005], n, m;
long long nr, v[1005];
struct Hash
{
long long n, m, power, hash;
void init (char *s, long long len)
{
power = 1, hash = 0;
for(long long i = len - 1; i >= 0; --i)
{
hash = (hash + (1LL * power * s[i]) % m) % m;
if(i)
power = (power * n) % m;
}
}
void roll (char toRemove, char toADD)
{
hash = (((hash - toRemove * power + m) * n) % m + toADD) % m;
}
};
int main()
{
f >> p >> t;
n = strlen(p);
m = strlen(t);
Hash pHash{31,40099}, tHash {31,40099};
Hash oHash{53,319993}, qHash {53,319993};
pHash.init(p, n);
tHash.init(t, n);
oHash.init(p, n);
qHash.init(t, n);
if(pHash.hash == tHash.hash && oHash.hash == qHash.hash)
{
v[++ nr] = 0;
}
for(long long i = n; i < m; i ++)
{
tHash.roll(t[i - n], t[i]);
qHash.roll(t[i - n], t[i]);
if(pHash.hash == tHash.hash && oHash.hash == qHash.hash)
{
if(nr <= 1000)
v[++ nr] = i - n + 1;
else
nr ++;
}
}
g << nr << '\n';
if(nr > 1000)
nr = 1000;
for(long long i = 1; i <= nr; i ++)
g << v[i] << ' ';
return 0;
}