Pagini recente » Cod sursa (job #1019929) | Cod sursa (job #1336246) | Cod sursa (job #2896976) | Cod sursa (job #993008) | Cod sursa (job #2083005)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int mod1 = 100007;
const int mod2 = 100021;
const int base = 131;
const int lmax = 2000005;
char s1[lmax], s2[lmax];
int bp1, bp2, hash1, hash2, hashb1, hashb2, n, m, i, ns, sol[1005];
int main() {
f.getline(s1+1,sizeof(s1));
f.getline(s2+1,sizeof(s2));
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+mod1)*base+s2[i])%mod1;
hashb2 = (( (hashb2 - (bp2*s2[i-n]) )%mod2+mod2)*base+s2[i])%mod2;
if (hash1==hashb1 && hash2==hashb2) {
ns++;
if (ns <1000) sol[ns] = i-n;
}
}
g << ns << '\n';
for (i = 1; i <= min(ns,1000); i++)
g << sol[i] << ' ';
}