Pagini recente » tema | Cod sursa (job #3134363) | Cod sursa (job #1921404) | Cod sursa (job #1092908) | Cod sursa (job #3239865)
#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> 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();
long long hashA = 0;
long long p_pow = 1;
for (int i = 0; i < lenA; i++) {
hashA = (hashA + charToValue(A[i]) * p_pow) % MOD;
p_pow = (p_pow * P) % MOD;
}
hashB.resize(lenB + 1, 0);
p_pow = 1;
for (int i = 0; i < lenB; i++) {
hashB[i + 1] = (hashB[i] + charToValue(B[i]) * p_pow) % MOD;
p_pow = (p_pow * P) % MOD;
}
p_pow = 1;
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 % MOD) {
matches.push_back(i);
}
p_pow = (p_pow * P) % MOD;
}
fout << matches.size() << "\n";
for (int i = 0; i < min((int)matches.size(), MAX_MATCHES); i++) {
fout << matches[i] << " ";
}
fout << "\n";
return 0;
}