Pagini recente » Cod sursa (job #1560931) | Cod sursa (job #2477932) | Cod sursa (job #736437) | Cod sursa (job #766343) | Cod sursa (job #2794725)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int P = 'z' + 1;
const int MOD1 = 100007;
const int MOD2 = 100009;
const int mxN = 2e6+5;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A, B;
int n, ap[mxN];
int main() {
f >> A >> B;
if (A.size() > B.size()) {
g << 0;
return 0;
}
for (int i = 0; i < A.size(); i++)
A[i] -= 'A';
for (int i = A.size(); i < B.size(); i++)
B[i] -= 'A';
int hA1 = 0;
int hA2 = 0;
int p1 = 1;
int p2 = 1;
for (int i = 0; i < A.size(); i++) {
hA1 = (hA1 * P + A[i]) % MOD1;
hA2 = (hA2 * P + A[i]) % MOD2;
if (i != 0) {
p1 = (p1 * P) % MOD1;
p2 = (p2 * P) % MOD2;
}
}
int hB1 = 0;
int hB2 = 0;
for (int i = 0; A[i]; i++) {
hB1 = (hB1 * P + B[i]) % MOD1;
hB2 = (hB2 * P + B[i]) % MOD2;
}
if (hA1 == hB1 && hA2 == hB2)
n++;
for (int i = A.size(); i < B.size(); i++) {
hB1 = ((hB1 - (B[i - A.size()] * p1) % MOD1 + MOD1) * P + B[i]) % MOD1;
hB2 = ((hB2 - (B[i - A.size()] * p2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if (hA1 == hB1 && hA2 == hB2) {
ap[i - A.size() + 1] = 1;
n++;
}
}
g << n << '\n';
int nr = 0;
for (int i = 0; i < B.size() && nr < 1000; i++)
if (ap[i]) {
g << i << ' ';
nr++;
}
return 0;
}