Pagini recente » Cod sursa (job #2537531) | Cod sursa (job #2805693) | Cod sursa (job #2492890) | Cod sursa (job #2839728) | Cod sursa (job #2792395)
#include <fstream>
#include <cstring>
#define NMAX 2000005
#define HASH 256
#define MOD 666013
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
char s[NMAX], v[NMAX];
int rez[NMAX];
int i;
int calculeazahash(char s[], int lg)
{
int h = 0;
i = 0;
while (i < lg)
{
h = (h * HASH + s[i]) % MOD;
++i;
}
return h;
}
int adauga(int h, char ch)
{
h = (h * HASH + ch) % MOD;
return h;
}
int scoate(int h, char ch, int put)
{
h = h - (ch * put) % MOD;
if (h < 0)
h = h + HASH;
return h;
}
int lgput (int a, int n)
{
int p = 1;
while (n > 0)
{
if (n % 2 == 1)
{
p = (long long)(p * a) % MOD;
}
a = (long long)(a * a) % MOD;
n = n / 2;
}
return p;
}
bool verif(char v[], char s[])
{
int j = 0;
while (v[j] && s[j])
{
if (v[j] != s[j])
return 0;
++j;
}
return 1;
}
int main()
{
int cnt = 0;
in.getline(s, NMAX);
in.getline(v, NMAX);
int shash, vhash;
int n = strlen(s);
int m = strlen(v);
i = 0;
shash = calculeazahash(s, n);
vhash = calculeazahash(v, n - 1);
++i;
int put = lgput(HASH, n - 1);
while (i <= m)
{
vhash = adauga(vhash, v[i - 1]);
if (shash == vhash)
{
if (verif(v + i - n, s))
{
rez[++cnt] = i - n;
}
}
vhash = scoate(vhash, v[i - n], put);
++i;
}
out << cnt << '\n';
for (i = 1; i <= cnt; i++)
out << rez[i] << " ";
return 0;
}