fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. ll p;
  7. string s;
  8. const int base = 32;
  9. const int N = 1e3 + 4;
  10. ll POW[N];
  11. ll hash_[N];
  12. ll q;
  13. vector<vector<pair<ll, ll>>> v;
  14.  
  15. ll get(int i, int j) {
  16.     return (hash_[j] - hash_[i - 1] * POW[j - i + 1] + p * p) % p;
  17. }
  18.  
  19. int main() {
  20.     ios_base::sync_with_stdio(false);
  21.     cin.tie(0);
  22.  
  23.     cin >> p >> q;
  24.     cin >> s;
  25.     int n = s.size();
  26.     POW[0] = 1;
  27.     for (int i = 1; i <= n; ++i) {
  28.         POW[i] = (POW[i - 1] * base) % p;
  29.     }
  30.     s = " " + s;
  31.     for (int i = 1; i <= n; ++i) {
  32.         hash_[i] = (hash_[i - 1] * base + s[i] - 'a' + 1) % p;
  33.     }
  34.     v.resize(n + 1);
  35.     for (int i = 1; i <= n; ++i) {
  36.         for (int j = i; j <= n; ++j) {
  37.             v[j - i + 1].push_back({get(i, j), i});
  38.         }
  39.     }
  40.     for (int i = 1; i <= n; ++i) {
  41.         sort(v[i].begin(), v[i].end());
  42.     }
  43.     while (q--) {
  44.         string t;
  45.         cin >> t;
  46.         int m = t.size();
  47.         ll hash_t = 0;
  48.         t = " " + t;
  49.         for (int i = 1; i <= m; ++i) {
  50.             hash_t = (hash_t * base + t[i] - 'a' + 1) % p; 
  51.         }
  52.         pair<ll, ll> check = {hash_t, 0};
  53.         auto it = lower_bound(v[m].begin(), v[m].end(), check);
  54.         int idx = it - v[m].begin();
  55.         if (it == v[m].end() || v[m][idx].first != hash_t) {
  56.             cout << "-1" << '\n';
  57.         } 
  58.         else {
  59.             cout << v[m][idx].second - 1 << '\n';
  60.         }
  61.     }   
  62.     return 0;
  63. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1DLldO
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

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!