Pagini recente » Cod sursa (job #2296783) | Cod sursa (job #945232) | Cod sursa (job #109815) | Cod sursa (job #2711943) | Cod sursa (job #2284498)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
#define NMAX 2000005
char p[NMAX], t[NMAX], n, m;
long long nr, v[1000], k = 0;
struct Hash
{
long long n, m, power, hash;
void init (char *s, int len)
{
power = 1, hash = 0;
for(int i = len - 1; i >= 0; --i)
{
hash = (hash + 1LL * power * s[i]) % 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{3, 666013}, tHash {3, 666013};
Hash oHash{3, 666013}, qHash {3, 666013};
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(int 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(int i = 1; i <= nr; i ++)
g << v[i] << ' ';
return 0;
}