fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // Ham tinh hash cho mot chuoi (chi goi 1 lan cho t)
  5. int hashing(const string &st, int p, int base) {
  6.     long long hash = 0;
  7.     for (char c : st)
  8.         hash = (hash * base + (c - 'a' + 1)) % p;
  9.     return hash;
  10. }
  11.  
  12. int main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(nullptr);
  15.     cout.tie(nullptr);
  16.  
  17.     int p;
  18.     string s, t;
  19.     cin >> p >> s >> t;
  20.  
  21.     int n = s.size(), m = t.size();
  22.     const int base = 32;
  23.  
  24.     // Tinh hash cho chuoi t
  25.     int hash_t = hashing(t, p, base);
  26.  
  27.     long long hash_s = 0, power = 1;
  28.  
  29.     // Tinh base^(m-1) % p de dung trong rolling hash
  30.     for (int i = 0; i < m - 1; ++i)
  31.         power = (power * base) % p;
  32.  
  33.     // Tinh hash cho m ky tu dau tien trong s
  34.     for (int i = 0; i < m; ++i)
  35.         hash_s = (hash_s * base + (s[i] - 'a' + 1)) % p;
  36.  
  37.     // So sanh lan dau tien
  38.     if (hash_s == hash_t) {
  39.         bool match = true;
  40.         for (int j = 0; j < m; ++j)
  41.             if (s[j] != t[j]) {
  42.                 match = false;
  43.                 break;
  44.             }
  45.         if (match) {
  46.             cout << 0;
  47.             return 0;
  48.         }
  49.     }
  50.  
  51.     // Sliding window + rolling hash
  52.     for (int i = m; i < n; ++i) {
  53.         // Loai ky tu cu o dau va them ky tu moi o cuoi
  54.         hash_s = (hash_s - (s[i - m] - 'a' + 1) * power % p + p) % p;
  55.         hash_s = (hash_s * base + (s[i] - 'a' + 1)) % p;
  56.  
  57.         // So sanh neu hash trung
  58.         if (hash_s == hash_t) {
  59.             bool match = true;
  60.             for (int j = 0; j < m; ++j)
  61.                 if (s[i - m + 1 + j] != t[j]) {
  62.                     match = false;
  63.                     break;
  64.                 }
  65.             if (match) {
  66.                 cout << i - m + 1;
  67.                 return 0;
  68.             }
  69.         }
  70.     }
  71.  
  72.     // Neu khong tim duoc vi tri phu hop
  73.     cout << -1;
  74. }
  75.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R92AR0
language:
C++ (gcc 8.3)
created:
7 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!