fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. long long power(int a, int b) {
  8.     const int m = 1e9 + 9;
  9.     const int p = 7; 
  10.  
  11.     long long result = a;
  12.     for (int i = 0; i < b; i++) {
  13.         result *= p;
  14.         result %= m;
  15.     }
  16.  
  17.     return result;
  18. }
  19.  
  20. long long compute_hash(string const& s) {
  21.     const int p = 7; 
  22.     const int m = 1e9 + 9;
  23.     long long hash_value = 0;
  24.     long long p_pow = 1;
  25.     for (char c : s) {
  26.         hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
  27.         p_pow = (p_pow * p) % m;
  28.     }
  29.  
  30.     return hash_value;
  31. }
  32.  
  33. long long rolling_hash(string const& previous_substring, long long previous_hash, char next_char) {
  34.     const int p = 7; 
  35.     const int m = 1e9 + 9;
  36.  
  37.     long long hash_value = ((previous_hash - (previous_substring[0] - 'a' + 1)) / p + power((next_char - 'a' + 1), previous_substring.length() - 1)) % m;
  38.  
  39.     return hash_value;
  40. }
  41.  
  42. int main()
  43. {
  44.  
  45.     string needle, haystack;
  46.     int needle_length, haystack_length;
  47.     long long needle_hash, substring_hash;
  48.     bool found;
  49.  
  50.     while (cin >> needle_length >> needle >> haystack) {
  51.         haystack_length = haystack.length();
  52.         needle_hash = compute_hash(needle);
  53.  
  54.         vector<pair<long long, int>> hashes;
  55.         substring_hash = compute_hash(haystack.substr(0, needle_length));
  56.         hashes.push_back({ substring_hash , 0 });
  57.  
  58.         for (int i = 1; i <= haystack_length - needle_length; i++) {
  59.             substring_hash = rolling_hash(haystack.substr(i - 1, needle_length), substring_hash, haystack[i + needle_length - 1]);
  60.             hashes.push_back({ substring_hash , i});
  61.         }
  62.         found = false;
  63.         for (int i = 0; i < hashes.size(); i++) {
  64.             if (hashes[i].first == needle_hash) {
  65.                 found = true;
  66.                 cout << hashes[i].second << '\n';
  67.             }
  68.         }
  69.         if (!found) cout << '\n';
  70.     }
  71.  
  72.  
  73.     return 0;
  74. }
  75.  
  76.  
Success #stdin #stdout 0s 5012KB
comments (?)
stdin
copy 
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo
stdout
copy 
2
4

3
9
15
21
https://ideone.com/vF5KNp
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!