Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <string>
- #include <vector>
- #define ull unsigned long long
- using namespace std;
- struct Hash {
- vector<ull> hash;
- vector<ull> pow;
- void build_hash(string& s, ull radix) {
- hash.resize(s.size());
- pow.resize(s.size());
- pow[0] = 1;
- hash[0] = s[0] - 'a' + 1;
- for (int i = 1; i < s.size(); ++i) {
- pow[i] = pow[i - 1] * radix;
- hash[i] = hash[i - 1] * radix + (s[i] - 'a' + 1);
- }
- }
- ull get_hash(int l, int r) {
- if (l == 0) {
- return hash[r];
- }
- return hash[r] - hash[l - 1] * pow[r - l + 1];
- }
- };
- int main() {
- string s, substring;
- int n;
- set<int> positions;
- Hash h1, h2;
- cin >> s >> substring;
- n = substring.size() - 1;
- h1.build_hash(s, 29);
- h2.build_hash(substring, 29);
- for (int i = 0; i < s.size() - n; ++i) {
- if (h2.get_hash(0, n) == h1.get_hash(i, i + n)) {
- positions.insert(i);
- }
- }
- cout << positions.size() << '\n';
- for (auto & pos : positions) {
- cout << pos << ' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement