Pagini recente » Cod sursa (job #2082426) | Cod sursa (job #3249063) | Cod sursa (job #177270) | Cod sursa (job #150280) | Cod sursa (job #3279861)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD = 1000000007, BASE = 256;
int a, b;
string A, B;
vector<int> matches;
// Modular exponentiation to compute BASE^(a-1) % MOD
long long modPow(int base, int exp, int mod) {
long long result = 1, power = base;
while (exp) {
if (exp % 2)
result = (result * power) % mod;
power = (power * power) % mod;
exp /= 2;
}
return result;
}
int main() {
fin >> A >> B;
a = A.size();
b = B.size();
if (a > b) {
fout << "0\n";
return 0;
}
int hashA = 0, curHashB = 0;
long long maxBaseInMod = modPow(BASE, a - 1, MOD);
// Compute initial hashes
for (int i = 0; i < a; i++) {
hashA = (hashA * BASE + A[i]) % MOD;
curHashB = (curHashB * BASE + B[i]) % MOD;
}
// Sliding window hash matching
for (int i = a; i <= b; i++) {
if (hashA == curHashB && A == B.substr(i - a, a))
matches.push_back(i - a);
if (i < b) {
curHashB = (curHashB - (maxBaseInMod * B[i - a]) % MOD + MOD) % MOD;
curHashB = (curHashB * BASE + B[i]) % MOD;
}
}
// Output results
fout << matches.size() << '\n';
for (size_t i = 0; i < min(matches.size(), (size_t)1000); i++)
fout << matches[i] << ' ';
return 0;
}