fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. const int mx = 1e6 + 5;
  6.  
  7. // --- CẤU HÌNH DOUBLE HASH ---
  8. // Dùng 2 bộ (Base, Mod) khác nhau để xác suất va chạm (Collision) gần như bằng 0.
  9. // Nếu chỉ dùng 1 bộ, các test hiểm của CSES sẽ đánh lừa được thuật toán.
  10. const ll MOD1 = 1e9 + 7;
  11. const ll BASE1 = 311; // Chọn số nguyên tố lớn hơn bảng chữ cái (256)
  12. const ll MOD2 = 1e9 + 9;
  13. const ll BASE2 = 317;
  14.  
  15. string t, p; // t: Text (văn bản), p: Pattern (mẫu)
  16.  
  17. // pw: Mảng lưu lũy thừa của Base (Base^0, Base^1, ...)
  18. // h: Mảng lưu giá trị Hash tiền tố (Prefix Hash)
  19. ll pw1[mx], h1[mx];
  20. ll pw2[mx], h2[mx];
  21.  
  22. // Hàm xây dựng bảng Hash cho chuỗi T
  23. void build_hash() {
  24.     int n = t.size();
  25.  
  26.     // Khởi tạo cơ sở
  27.     pw1[0] = pw2[0] = 1; // Base^0 luôn bằng 1
  28.     h1[0] = h2[0] = 0;   // Hash của chuỗi rỗng là 0
  29.  
  30.     for(int i = 0; i < n; ++i) {
  31.         // 1. Tính trước các lũy thừa của Base
  32.         // pw[i+1] = pw[i] * Base
  33.         pw1[i+1] = (pw1[i] * BASE1) % MOD1;
  34.         pw2[i+1] = (pw2[i] * BASE2) % MOD2;
  35.  
  36.         // 2. Tính Hash cộng dồn (Rolling Hash)
  37.         // Tư duy giống hệ thập phân: "45" -> thêm số 1 -> "451"
  38.         // Ta lấy số cũ (45) nhân 10 (Base) rồi cộng số mới (1)
  39.         h1[i+1] = (h1[i] * BASE1 + t[i]) % MOD1;
  40.         h2[i+1] = (h2[i] * BASE2 + t[i]) % MOD2;
  41.     }
  42. }
  43.  
  44. // Hàm lấy giá trị Hash của đoạn con từ i đến j
  45. // Lưu ý: i, j ở đây là chỉ số 1-based (theo mảng h và pw)
  46. pair<ll, ll> get_hash(int i, int j) { 
  47.     int len = j - i + 1; // Độ dài đoạn cần cắt
  48.  
  49.     // CÔNG THỨC QUAN TRỌNG:
  50.     // Hash(đoạn) = Hash(cuối) - Hash(đầu_thừa) * Base^len
  51.     // Ví dụ: Lấy "51" từ "4512". 
  52.     // Hash("451") - Hash("4") * 10^2 = 451 - 400 = 51.
  53.  
  54.     // Tính bộ 1:
  55.     ll v1 = (h1[j] - h1[i-1] * pw1[len] % MOD1 + MOD1) % MOD1;
  56.     // Giải thích đoạn "+ MOD1": 
  57.     // Phép trừ (A - B) % M có thể ra số âm nếu A < B (do A đã bị mod trước đó).
  58.     // Cộng thêm MOD để đảm bảo kết quả luôn dương.
  59.  
  60.     // Tính bộ 2:
  61.     ll v2 = (h2[j] - h2[i-1] * pw2[len] % MOD2 + MOD2) % MOD2;
  62.  
  63.     return {v1, v2}; // Trả về cặp hash để so sánh
  64. }
  65.  
  66. int main() {
  67.     cin.tie(0)->sync_with_stdio(0);
  68.     if(fopen("String_Matching.inp", "r")) {
  69.         freopen("String_Matching.inp", "r", stdin);
  70.         freopen("String_Matching.out", "w", stdout);
  71.     }
  72.  
  73.     cin >> t >> p;
  74.     int n = t.size();
  75.     int m = p.size();
  76.  
  77.     // Nếu mẫu dài hơn văn bản thì không bao giờ tìm thấy
  78.     if(m > n) {
  79.         cout << 0;
  80.         return 0;
  81.     }
  82.  
  83.     // Bước 1: Dựng hash cho văn bản T
  84.     build_hash();
  85.  
  86.     // Bước 2: Tính hash thủ công cho mẫu P
  87.     // Vì P ngắn và cố định, ta tính 1 lần duy nhất, không cần lưu mảng
  88.     ll hp1 = 0, hp2 = 0;
  89.     for(char c : p) {
  90.         hp1 = (hp1 * BASE1 + c) % MOD1;
  91.         hp2 = (hp2 * BASE2 + c) % MOD2;
  92.     }
  93.  
  94.     int ans = 0;
  95.  
  96.     // Bước 3: Cửa sổ trượt (Sliding Window)
  97.     // Duyệt qua tất cả các đoạn con có độ dài bằng m trong T
  98.     for(int i = 0; i <= n - m; ++i) {
  99.         // Lấy Hash đoạn T[i ... i+m-1]
  100.         // Vì mảng hash h1, h2 mình xây dựng theo chỉ số 1 (h[1] là ký tự đầu)
  101.         // Nên khi gọi get_hash phải cộng thêm 1 vào index: (i+1, i+m)
  102.         pair<ll, ll> curr = get_hash(i + 1, i + m);
  103.  
  104.         // Kiểm tra xem Hash đoạn này có bằng Hash của mẫu P không
  105.         // Phải khớp cả 2 bộ hash mới tính là đúng
  106.         if(curr.first == hp1 && curr.second == hp2) {
  107.             ans++;
  108.         }
  109.     }
  110.  
  111.     cout << ans;
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0.01s 9756KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/qZkcj1
language:
C++14 (gcc 8.3)
created:
4 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!