Pagini recente » Rating Bojoaga Petru Matei (Matei007) | Monitorul de evaluare | Cod sursa (job #1719401) | Cod sursa (job #2689939) | Cod sursa (job #2237966)
#include <bits/stdc++.h>
using namespace std;
// String Hasher
template <int B, int MOD>
struct Hasher {
// Static hash function
template <typename iter_type>
static int hash(iter_type begin, iter_type end) {
int h = 0;
for (iter_type it = begin; it != end; ++it)
h = (1LL * h * B + *it) % MOD;
return h;
}
// Data members
vector <int> pows, h;
// Constructor
template <typename iter_type>
Hasher(iter_type begin, iter_type end) {
const int sz = end - begin + 1;
pows.resize(sz), h.resize(sz);
pows[0] = 1, h[0] = 0;
for (iter_type it = begin; it != end; ++it) {
pows[it - begin + 1] = (1LL * pows[it - begin] * B) % MOD;
h[it - begin + 1] = (1LL * h[it - begin] * B + (*it)) % MOD;
}
}
// Continuous subsequence hash query[l, r]
int hash(int l, int r) {
int res = (h[r + 1] - 1LL * h[l] * pows[r - l + 1]) % MOD;
if (res < 0)
res += MOD;
return res;
}
};
typedef Hasher <263, 1000000000 + 7> H1;
//typedef Hasher <277, 1000000000 + 9> H2;
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string pattern, str;
cin >> pattern >> str;
int h_pat1 = H1 :: hash(pattern.begin(), pattern.end());
//int h_pat2 = H2 :: hash(pattern.begin(), pattern.end());
H1 h1(str.begin(), str.end());
//H2 h2(str.begin(), str.end());
vector <int> ans;
for (int i = 0; i + pattern.size() - 1 < str.size(); ++ i)
if (h1.hash(i, i + pattern.size() - 1) == h_pat1)// && h2.hash(i, i + pattern.size() - 1) == h_pat2)
ans.push_back(i);
cout << ans.size() << '\n';
if (ans.size() > 1000)
ans.resize(1000);
for (int i = 0; i < ans.size(); ++ i)
cout << ans[i] << " \n"[i + 1 == ans.size()];
return 0;
}