Pagini recente » Cod sursa (job #2563007) | Cod sursa (job #39140) | Cod sursa (job #97919) | Cod sursa (job #2571459) | Cod sursa (job #3005187)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int BASE = 26;
const int HASH1 = 1999997;
const int HASH2 = 1999993;
const int DIM = 2000010;
char a[DIM], b[DIM];
bool match[DIM];
int main() {
fin >> a >> b;
int lenA = strlen(a);
int lenB = strlen(b);
if (lenA > lenB) {
fout << 0;
return 0;
}
int p1 = 1, p2 = 1;
int hashA1 = 0, hashA2 = 0;
int hashB1 = 0, hashB2 = 0;
for (int i = 0; i < lenA; i++) {
hashA1 = (hashA1 * BASE + a[i]) % HASH1;
hashA2 = (hashA2 * BASE + a[i]) % HASH2;
hashB1 = (hashB1 * BASE + b[i]) % HASH1;
hashB2 = (hashB2 * BASE + b[i]) % HASH2;
if (i != 0) {
p1 = (p1 * BASE) % HASH1;
p2 = (p2 * BASE) % HASH2;
}
}
int matchCnt = 0;
if (hashA1 == hashB1 && hashA2 == hashB2) {
match[0] = true;
matchCnt++;
}
for (int i = lenA; i < lenB; i++) {
hashB1 = ((hashB1 - (p1 * b[i - lenA]) % HASH1 + HASH1) * BASE + b[i]) % HASH1;
hashB2 = ((hashB2 - (p2 * b[i - lenA]) % HASH2 + HASH2) * BASE + b[i]) % HASH2;
if (hashA1 == hashB1 && hashA2 == hashB2) {
match[i - lenA + 1] = true;
matchCnt++;
}
}
fout << matchCnt << '\n';
matchCnt = 0;
for (int i = 0; i < lenB && matchCnt < 1000; i++) {
if (match[i]) {
fout << i << ' ';
matchCnt++;
}
}
return 0;
}