Pagini recente » Cod sursa (job #2785436) | Cod sursa (job #2382721) | Cod sursa (job #2894799) | Cod sursa (job #39640) | Cod sursa (job #3279844)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const unsigned long long base = 257;
const unsigned long long mod = 1000000009ULL;
unsigned long long calculateHash(const string& s) {
unsigned long long h = 0;
for (char c : s) {
h = (h * base + (unsigned char)c) % mod;
}
return h;
}
unsigned long long updateHash(unsigned long long oldHash, char removed, char added, unsigned long long basePower) {
oldHash = (oldHash + mod - (unsigned long long)(unsigned char)removed * basePower % mod) % mod;
oldHash = (oldHash * base + (unsigned char)added) % mod;
return oldHash;
}
bool checkSubstring(const string& B, int start, const string& A) {
if (start + (int)A.size() > (int)B.size()) return false;
return (B.compare(start, A.size(), A) == 0);
}
vector<int> findSubstrings(const string& A, const string& B) {
int n = (int)A.size(), m = (int)B.size();
vector<int> r;
if (n > m) return r;
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 && checkSubstring(B, 0, A)) {
r.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 && checkSubstring(B, i, A)) {
r.push_back(i);
}
}
return r;
}
int main() {
ios::sync_with_stdio(false);
in.tie(nullptr);
string A, B;
in >> A >> B;
vector<int> appearances = findSubstrings(A, B);
out << (int)appearances.size() << "\n";
int limit = (int)appearances.size();
if (limit > 1000) limit = 1000;
for (int i = 0; i < limit; i++) {
out << appearances[i] << " ";
}
out << "\n";
return 0;
}