fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Khai báo 2 bộ modulo nguyên tố đủ lớn để tránh collision
  5. const long long MOD1 = 1e9 + 7;
  6. const long long MOD2 = 1e9 + 9;
  7.  
  8. // Khai báo 2 cơ số (Base) lớn hơn kích thước bảng chữ cái (thường dùng số nguyên tố > 256)
  9. const long long BASE1 = 311;
  10. const long long BASE2 = 317;
  11.  
  12. int main() {
  13.     ios_base::sync_with_stdio(false);
  14.     cin.tie(NULL);
  15.  
  16.     string A = "ababcabcabababa";
  17.     string B = "aba";
  18.  
  19.     int n = A.length();
  20.     int m = B.length();
  21.  
  22.  
  23.     // Tiền xử lý mảng lũy thừa cơ số
  24.     vector<long long> pow1(n + 1, 1), pow2(n + 1, 1);
  25.     for (int i = 1; i <= n; ++i) {
  26.         pow1[i] = (pow1[i - 1] * BASE1) % MOD1;
  27.         pow2[i] = (pow2[i - 1] * BASE2) % MOD2;
  28.     }
  29.  
  30.     // Tiền xử lý mảng Hash tiền tố cho xâu A
  31.     // h1[i] lưu hash của tiền tố A[0...i-1]
  32.     vector<long long> h1(n + 1, 0), h2(n + 1, 0);
  33.     for (int i = 0; i < n; ++i) {
  34.         h1[i + 1] = (h1[i] * BASE1 + A[i]) % MOD1;
  35.         h2[i + 1] = (h2[i] * BASE2 + A[i]) % MOD2;
  36.     }
  37.  
  38.     // 3. Tính giá trị Hash kép cho xâu mẫu B
  39.     long long hashB1 = 0, hashB2 = 0;
  40.     for (int i = 0; i < m; ++i) {
  41.         hashB1 = (hashB1 * BASE1 + B[i]) % MOD1;
  42.         hashB2 = (hashB2 * BASE2 + B[i]) % MOD2;
  43.     }
  44.  
  45.  
  46.     // Duyệt qua tất cả cửa sổ độ dài m trong xâu A để so sánh
  47.     cout << "Xau A: " << A << "\n";
  48.     cout << "Xau B: " << B << "\n";
  49.     cout << "Cac vi tri xau B xuat hien trong A (0-indexed):\n";
  50.  
  51.     vector<int> matches;
  52.     for (int i = 0; i <= n - m; ++i) {
  53.         // Lấy Hash của đoạn A[i ... i + m - 1]
  54.         long long res1 = (h1[i + m] - (h1[i] * pow1[m]) % MOD1 + MOD1) % MOD1;
  55.         long long res2 = (h2[i + m] - (h2[i] * pow2[m]) % MOD2 + MOD2) % MOD2;
  56.  
  57.         // So sánh đồng thời cả 2 giá trị Hash
  58.         if (res1 == hashB1 && res2 == hashB2) {
  59.             matches.push_back(i);
  60.         }
  61.     }
  62.  
  63.     // In kết quả
  64.     for (int pos : matches) {
  65.         cout << "Vi tri " << pos << " -> " << A.substr(pos, m) << "\n";
  66.     }
  67.  
  68.     return 0;
  69. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Xau A: ababcabcabababa
Xau B: aba
Cac vi tri xau B xuat hien trong A (0-indexed):
Vi tri 0 -> aba
Vi tri 8 -> aba
Vi tri 10 -> aba
Vi tri 12 -> aba
https://ideone.com/kldyoH
Demo double hash (modulo)
language:
C++14 (gcc 8.3)
created:
5 hours 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!