Pagini recente » Cod sursa (job #327308) | Cod sursa (job #2954666) | Cod sursa (job #2955615) | Cod sursa (job #1097021) | Cod sursa (job #2792609)
#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], n, m, 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 + MOD;
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()
{
in.getline(s, NMAX);
in.getline(v, NMAX);
int shash, vhash, put, cnt = 0;
n = strlen(s);
m = strlen(v);
i = 0;
shash = calculeazahash(s, n);
vhash = calculeazahash(v, n - 1);
//out << shash << " " << vhash << '\n';
++i;
put = lgput(HASH, n - 1);
while (i <= m)
{
vhash = adauga(vhash, v[i - 1]);
if (shash == vhash)
{
if (verif(v + i - n, s))
{
cnt++;
rez[cnt] = i - n;
}
}
//out << shash << " " << vhash << '\n';
vhash = scoate(vhash, v[i - n], put);
++i;
}
out << cnt << '\n';
for (i = 1; i <= cnt; i++)
out << rez[i] << " ";
return 0;
}