Pagini recente » Cod sursa (job #1317932) | Cod sursa (job #746010) | Cod sursa (job #2131568) | Cod sursa (job #1914032) | Cod sursa (job #1626953)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const int P = 73;
const int M1 = 100007, M2 = 100021, Nmax = 2000666;
string A, B;
int hash1 = 0, hash2 = 0, h1 = 0, h2 = 0, N = 0, ans[Nmax];
int p1 = 1, p2 = 1;
int main() {
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
fin >> A >> B;
int na = A.size();
for (size_t i = 0; i < A.size(); ++i) {
if (i != 0) {
p1 = (p1 * P) % M1;
p2 = (p2 * P) % M2;
}
hash1 = (hash1 * P + A[i]) % M1;
hash2 = (hash2 * P + A[i]) % M2;
}
for (size_t i = 0; i < A.size(); ++i) {
h1 = (h1 * P + B[i]) % M1;
h2 = (h2 * P + B[i]) % M2;
}
if (h1 == hash1 && h2 == hash2) {
ans[N] = 0;
++N;
}
for (size_t i = A.size(); i < B.size(); ++i) {
h1 = ((h1 - (p1 * B[i - na]) % M1 + M1) * P + B[i]) % M1;
h2 = ((h2 - (p2 * B[i - na]) % M2 + M2) * P + B[i]) % M2;
if(h1 == hash1 && h2 == hash2) {
if (N < 1000) {
ans[N] = i - na + 1;
}
++N;
}
}
fout << N << endl;
for (int i = 0; i < N && i < 1000; ++i) {
fout << ans[i] << ' ';
}
fout << endl;
return 0;
}