Pagini recente » Cod sursa (job #1641866) | pre_oni_gim2015 | Cod sursa (job #738097) | Cod sursa (job #2636852) | Cod sursa (job #2794640)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int P = 80;
const int MOD = 100007;
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())
return 0;
int hA = 0;
int p = 1;
for (int i = 0; i < A.size(); i++) {
hA = (hA * P + A[i]) % MOD;
if (i != 0)
p = (p * P) % MOD;
}
int hB = 0;
for (int i = 0; A[i]; i++) {
hB = (hB * P + B[i]) % MOD;
}
if (hA == hB)
n++;
for (int i = A.size(); i < B.size(); i++) {
hB = ((hB - (B[i - A.size()] * p) % MOD + MOD) * P + B[i]) % MOD;
if (hA == hB) {
ap[i - A.size() + 1] = 1;
n++;
}
}
g << n << '\n';
for (int i = 0; i < B.size(); i++)
if (ap[i])
g << i << ' ';
return 0;
}