Pagini recente » Istoria paginii runda/wettbewerbssimulation/clasament | Cod sursa (job #1814379) | Cod sursa (job #2644755) | Cod sursa (job #1610799) | Cod sursa (job #3239864)
#include <bits/stdc++.h>
#include <vector>
using namespace std;
std::string file = "strmatch";
std::ifstream fin(file + ".in");
std::ofstream fout(file + ".out");
// #define fin std::cin
// #define fout std::cout
const int MOD = 1e9 + 7;
const int P = 31;
const int MAX_MATCHES = 1000;
int charToValue(char c) {
if (c >= 'a' && c <= 'z')
return c - 'a' + 1;
if (c >= 'A' && c <= 'Z')
return c - 'A' + 27; // 26 letters in lowercase + 1
if (c >= '0' && c <= '9')
return c - '0' + 53; // 26 lowercase + 26 uppercase + 1
return 0;
}
std::vector<long long> p_pow, hashB;
std::vector<int> matches;
int main(int argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string A, B;
fin >> A >> B;
int lenA = A.size();
int lenB = B.size();
p_pow.resize(max(lenA, lenB) + 1);
p_pow[0] = 1;
for (int i = 1; i <= max(lenA, lenB); i++) {
p_pow[i] = (p_pow[i - 1] * P) % MOD;
}
long long hashA = 0;
for (int i = 0; i < lenA; i++) {
hashA = (hashA + charToValue(A[i]) * p_pow[i]) % MOD;
}
hashB.resize(lenB + 1, 0);
for (int i = 0; i < lenB; i++) {
hashB[i + 1] = (hashB[i] + charToValue(B[i]) * p_pow[i]) % MOD;
}
for (int i = 0; i + lenA <= lenB; i++) {
long long current_hash = (hashB[i + lenA] + MOD - hashB[i]) % MOD;
if (current_hash == hashA * p_pow[i] % MOD) {
matches.push_back(i);
}
}
fout << matches.size() << "\n";
for (int i = 0; i < min((int)matches.size(), MAX_MATCHES); i++) {
fout << matches[i] << " ";
}
fout << "\n";
return 0;
}