Pagini recente » Cod sursa (job #3351619) | Cod sursa (job #2443480) | Cod sursa (job #3312890) | Cod sursa (job #519822) | Cod sursa (job #3340625)
/// patratele
#include <bits/stdc++.h>
using namespace std;
#define MOD1 100021
#define MOD2 100007
#define Baza 97
#define NMAX 2000005
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long i, la, lb, hasha1, hasha2, hashb1, hashb2, ras[NMAX], vf, p1, p2;
char a[NMAX], b[NMAX];
int main()
{
// ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fin >> a >> b;
la = strlen(a);
lb = strlen(b);
p1=p2=1;
for (i = 0; i < la; i++)
{
hasha1 = (hasha1 * Baza % MOD1 + a[i])%MOD1;
hasha2 = (hasha2 * Baza % MOD2 + a[i])%MOD2;
hashb1 = (hashb1 * Baza % MOD1 + b[i])%MOD1;
hashb2 = (hashb2 * Baza % MOD2 + b[i])%MOD2;
if (i != 0)
{
p1 = p1 * Baza % MOD1;
p2 = p2 * Baza % MOD2;
}
}
if (hasha1 == hashb1 && hasha2 == hashb2)
ras[++vf] = 0;
for (i = la; i < lb; i++)
{
hashb1 = ((hashb1 + MOD1 - (p1 * b[i - la] % MOD1))%MOD1 * Baza % MOD1 + b[i]) % MOD1;
hashb2 = ((hashb2 + MOD2 - (p2 * b[i - la] % MOD2))%MOD2 * Baza % MOD2 + b[i]) % MOD2;
if (hasha1 == hashb1 && hasha2 == hashb2)
ras[++vf] = i - la + 1;
}
fout << vf << '\n';
for (i = 1; i <= min(vf, 1000ll); i++)
fout << ras[i] << " ";
return 0;
}