Pagini recente » Cod sursa (job #932213) | Cod sursa (job #2982387) | Cod sursa (job #1146085) | Cod sursa (job #1322928) | Cod sursa (job #3277808)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const unsigned long long base = 31;
const unsigned long long mod = 1e9 + 9;
unsigned long long calculateHash(const string& s) {
unsigned long long hash = 0;
for (char c : s) {
hash = (hash * base + c) % mod;
}
return hash;
}
unsigned long long updateHash(unsigned long long oldHash, char removed, char added, unsigned long long basePower) {
oldHash = (oldHash - removed * basePower % mod + mod) % mod;
oldHash = (oldHash * base + added) % mod;
return oldHash;
}
vector<int> findSubstrings(const string& A, const string& B) {
int n = A.size(), m = B.size();
vector<int> result;
if (n > m) return result;
unsigned long long hashA = calculateHash(A);
unsigned long long hashB = calculateHash(B.substr(0, n));
unsigned long long basePower = 1;
for (int i = 0; i < n - 1; ++i) {
basePower = (basePower * base) % mod;
}
if (hashA == hashB) {
result.push_back(0);
}
for (int i = 1; i <= m - n; ++i) {
hashB = updateHash(hashB, B[i - 1], B[i + n - 1], basePower);
if (hashA == hashB) {
result.push_back(i);
}
}
return result;
}
int main() {
string A, B;
in >> A >> B;
vector<int> appearances = findSubstrings(A, B);
if (!appearances.empty()) {
out << appearances.size() << '\n';
for (int pos : appearances) {
out << pos << " ";
}
out << '\n';
}
return 0;
}