Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <vector>
- using namespace std;
- typedef long long ll;
- const int alphabet_size = 26;
- const int base = 53;
- const ll MOD = 922337186621;
- void rolling_hash(string & s, int window_size, string & pattern) {
- int n = (int) s.size();
- vector<ll> powers(n + 1, 1);
- for(int i = 1; i <= n; i++) {
- powers[i] = (powers[i - 1] * alphabet_size) % MOD;
- }
- ll hash = 0;
- ll res_hash = 0;
- set<pair<ll, ll> > st;
- for(int i = 0; i < window_size; i++) {
- res_hash = (res_hash * alphabet_size + pattern[i]) % MOD;
- }
- for(int i = 0; i < window_size; i++) {
- hash = (hash * alphabet_size + s[i]) % MOD;
- }
- int res =0 ;
- if(hash == res_hash) {
- bool ok = true;
- for(int j = 0; j < window_size; j++) {
- if(pattern[j] != s[j]) {
- ok = false;
- break;
- }
- }
- if(ok) {
- cout << 0 << endl;
- }
- }
- for(int i = 1; i <= n - window_size; i++) {
- hash = (hash - powers[window_size - 1] * s[i - 1]);
- while (hash < 0) {
- hash += MOD;
- }
- hash %= MOD;
- hash = (hash * alphabet_size + s[i + window_size - 1]) % MOD;
- if(hash == res_hash) {
- bool ok = true;
- for(int j = 0; j < window_size; j++) {
- if(pattern[j] != s[i + j]) {
- ok = false;
- break;
- }
- }
- if(ok) {
- cout << i << endl;
- }
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- int win_size;
- string text, pattern;
- while(cin >> win_size >> pattern >> text) {
- rolling_hash(text, win_size, pattern);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement