Pagini recente » Cod sursa (job #2441385) | Cod sursa (job #1178799) | Cod sursa (job #1521063) | Cod sursa (job #53990) | Cod sursa (job #2082987)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1 = 10000007;
const int mod2 = 10000021;
const int base = 131;
const int lmax = 2000005;
char s1[lmax], s2[lmax];
long long bp1, bp2, hash1, hash2, hashb1, hashb2, n, m, i, ns, sol[1005];
int main() {
f >> (s1+1) >> (s2+1);
n = strlen(s1+1), m = strlen(s2+1);
if (n > m) { g << 0; return 0;}
bp1 = bp2 = 1;
for (i = 1; i <= n; i++) {
hash1 = (hash1 *base+s1[i])%mod1;
hash2 = (hash2 *base+s1[i])%mod2;
hashb1 = (hashb1*base+s2[i])%mod1;
hashb2 = (hashb2*base+s2[i])%mod2;
if (i > 1)
bp1 = (bp1*base)%mod1, bp2 = (bp2*base)%mod2;
}
if (hash1==hashb1 && hash2==hashb2) {
ns++;
if (ns <1000) sol[ns] = 0;
}
for (i = n+1; i <= m; i++) {
/*hashb1 = hashb1 - (bp1*s2[i-n])%mod1;
hashb2 = hashb2 - (bp2*s2[i-n])%mod2;*/
hashb1 = (((hashb1 - (bp1*s2[i-n])%mod1+mod1)%mod1*base)%mod1+s2[i])%mod1;
hashb2 = (((hashb2 - (bp2*s2[i-n])%mod2+mod2)%mod2*base)%mod2+s2[i])%mod2;
//g << hash1 << ' ' << hashb1 << ' ' << hash2 << ' ' << hashb2 << ' ' << '\n';
if (hash1==hashb1 && hash2==hashb2) {
ns++;
if (ns <1000) sol[ns] = i-n;
}
}
g << ns << '\n';
for (i = 1; i <= min(ns,1LL*1000); i++)
g << sol[i] << ' ';
}