Pagini recente » Cod sursa (job #1726679) | Cod sursa (job #2962212) | Cod sursa (job #3245870) | Cod sursa (job #2835935) | Cod sursa (job #2284403)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
struct Hash
{
int 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()
{
char p[100], t[100], n, m;
int nr = 0, v[1000], k = 0;
f >> p >> t;
n = strlen(p);
m = strlen(t);
Hash pHash{3, 666013}, tHash {3, 666013};
pHash.init(p, n);
tHash.init(t, n);
if(pHash.hash == tHash.hash)
{
nr ++;
v[k ++] = 0;
}
for(int i = n; i < m; i ++)
{
tHash.roll(t[i - n], t[i]);
if(pHash.hash == tHash.hash)
{
nr ++;
v[k ++] = i - n + 1;
}
}
if(n > 1000)
{
g << nr << '\n';
for(int i = 0; i <= 1000; i ++)
g << v[i] << ' ';
}
else
{
g << nr << '\n';
for(int i = 0; i < k; i ++)
g << v[i] << ' ';
}
return 0;
}