Pagini recente » Cod sursa (job #814653) | Cod sursa (job #2171798) | Cod sursa (job #1902848) | Cod sursa (job #643082) | Cod sursa (job #3224529)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#define NMAX 2000000
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define P 73
#define MOD1 100007
#define MOD2 100021
char A[NMAX+5], B[NMAX+5];
int la, lb;
int hashA1, hashA2, hashB1, hashB2, nr;
bool match[NMAX+5];
int main() {
fin >> A >> B;
la = strlen(A);
lb = strlen(B);
if (la > lb) {
fout << "0\n";
return 0;
}
int powP1 = 1, powP2 = 1;
for (int i = 0; i<la; i++) {
hashA1 = (hashA1*P + A[i])%MOD1;
hashA2 = (hashA2*P + A[i])%MOD2;
hashB1 = (hashB1*P + B[i])%MOD1;
hashB2 = (hashB2*P + B[i])%MOD2;
if (i != 0) powP1 = (powP1 * P) % MOD1;
if (i != 0) powP2 = (powP2 * P) % MOD2;
}
if (hashA1 == hashB1 && hashA2 == hashB2) {
match[0] = 1;
nr++;
}
for (int i = la; i<lb; i++) {
hashB1 = (((hashB1 - B[i-la]*powP1) % MOD1 + MOD1) * P + B[i]) % MOD1;
hashB2 = (((hashB2 - B[i-la]*powP2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2) {
match[i-la+1] = 1;
nr++;
}
}
fout << nr << "\n";
nr = 0;
for (int i = 0; i<lb && nr < 1000; i++) {
if (match[i]) {
fout << i << " ";
nr++;
}
}
return 0;
}