Pagini recente » Cod sursa (job #85963) | Cod sursa (job #20092) | Cod sursa (job #2331153) | Cod sursa (job #2657941) | Cod sursa (job #3279849)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
static const unsigned long long base1 = 31ULL;
static const unsigned long long mod1 = 1000000009ULL;
static const unsigned long long base2 = 53ULL;
static const unsigned long long mod2 = 1000000007ULL;
struct TwoHash {
unsigned long long h1, h2;
};
TwoHash calcHash(const string &s) {
TwoHash H{0ULL, 0ULL};
for (char c : s) {
unsigned char uc = (unsigned char)c;
H.h1 = (H.h1 * base1 + uc) % mod1;
H.h2 = (H.h2 * base2 + uc) % mod2;
}
return H;
}
TwoHash updateHash(const TwoHash &oldH, char removed, char added, unsigned long long p1, unsigned long long p2) {
TwoHash nH = oldH;
unsigned long long r = (unsigned char)removed;
unsigned long long a = (unsigned char)added;
nH.h1 = (nH.h1 + mod1 - (r * p1) % mod1) % mod1;
nH.h1 = (nH.h1 * base1 + a) % mod1;
nH.h2 = (nH.h2 + mod2 - (r * p2) % mod2) % mod2;
nH.h2 = (nH.h2 * base2 + a) % mod2;
return nH;
}
vector<int> findSubstrings(const string &A, const string &B) {
int n = (int)A.size();
int m = (int)B.size();
vector<int> r;
if (n > m) return r;
TwoHash hA = calcHash(A);
TwoHash hB = calcHash(B.substr(0, n));
unsigned long long p1 = 1ULL, p2 = 1ULL;
for (int i = 0; i < n - 1; i++) {
p1 = (p1 * base1) % mod1;
p2 = (p2 * base2) % mod2;
}
if (hA.h1 == hB.h1 && hA.h2 == hB.h2) {
r.push_back(0);
}
for (int i = 1; i <= m - n; i++) {
hB = updateHash(hB, B[i - 1], B[i + n - 1], p1, p2);
if (hB.h1 == hA.h1 && hB.h2 == hA.h2) {
r.push_back(i);
}
}
return r;
}
int main() {
ios::sync_with_stdio(false);
in.tie(nullptr);
string A, B;
in >> A >> B;
vector<int> ans = findSubstrings(A, B);
out << (int)ans.size() << "\n";
int limit = ans.size();
if (limit > 1000) limit = 1000;
for (int i = 0; i < limit; i++) {
out << ans[i] << " ";
}
out << "\n";
return 0;
}