vi
new
+9
Avatar
Viblo Algorithm @algorithm
10.4K 781 122
Đã đăng vào thg 12 26, 2022 10:20 SA 18 phút đọc
2.4K

Giải thuật so khớp chuỗi Rolling Hash

I. Đặt vấn đề

Trong lập trình thi đấu nói riêng và trong khoa học máy tính nói chung, vấn đề xử lý chuỗi kí tự là vấn đề rất phổ biến. Các bài toán về chuỗi vô cùng đa dạng, và một trong số những dạng toán hay gặp chính là tìm kiếm và so khớp chuỗi. Bài toán dưới đây là một ví dụ cơ bản nhất:

"Cho một chuỗi kí tự AA độ dài N (1≤N≤105)N \ (1 \le N \le 10^5) và một chuỗi kí tự BB độ dài M (1≤M≤105)M \ (1 \le M \le 10^5). Cần trả lời câu hỏi: Chuỗi kí tự BB xuất hiện bao nhiêu lần trong chuỗi kí tự A?A?"

Có rất nhiều giải thuật để xử lý bài toán này, phổ biến nhất trong các kỳ thi là:

  • Duyệt trâu bò (Brute-Force): Xét mọi chuỗi con độ dài MM trong chuỗi A,A, với mỗi chuỗi con ta so khớp nó với chuỗi BB. Giải thuật này có độ phức tạp O(N×M)O(N \times M).
  • Giải thuật KMP: Tên đầy đủ là Knuth-Morris-Pratt, là một giải thuật được phát minh bởi Donald Knuth, Vaughan Pratt và James H. Morris vào năm 19741974. Giải thuật này có tính hiệu quả rất cao, độ phức tạp chỉ là O(M+N),O(M + N), tuy nhiên cài đặt lại không đơn giản.
  • Rolling Hash: Còn gọi là giải thuật Rabin-Karp, nhưng ở Việt Nam thì có tên thường gọi là Hash - băm chuỗi. Đây là một giải thuật cũng rất hiệu quả, và rất được ưa chuộng trong các kỳ thi lập trình vì tính linh động khi sử dụng, cài đặt đơn giản và dễ hiểu.

Trong bài viết này, mình sẽ tập trung nói về ý tưởng của thuật toán Rolling Hash cùng một số ví dụ minh họa ứng dụng của giải thuật này. Các cài đặt đều sẽ sử dụng ngôn ngữ C++ để minh họa. Trước khi đọc bài viết này, bạn đọc cần có được kiến thức về Số học đồng dư cũng như nắm được các kiến thức cơ bản về xâu chuỗi.

II. Ý tưởng thuật toán

1. Mã hóa chuỗi dựa trên hệ cơ số

Như ta đã biết, mọi kí tự sử dụng trong ngôn ngữ lập trình đều nằm trong một bảng kí tự là ASCII, mỗi kí tự đều có đánh mã số riêng từ 00 tới 255255. Dựa vào điều này, ta sẽ mã hóa các chuỗi bằng số hiệu của chúng. Chẳng hạn, chuỗi kí tự abcd sau khi mã hóa sẽ trở thành dãy số: {97,98,99,100}\{97, 98, 99, 100\}.

Khi đó, kết hợp thêm các kiến thức về hệ cơ số vào giải thuật, ta sẽ hiểu rằng: Chuỗi kí tự đang được viết thành một dãy số ở hệ cơ số base, với base là một giá trị bất kỳ thỏa mãn: base phải lớn hơn giá trị mã hóa lớn nhất của các kí tự trong chuỗi. Với chuỗi abcd nói trên, base có thể là bất kỳ số nào bắt đầu từ 101101 trở lên. Còn nếu chuỗi chỉ là 12345 chẳng hạn, thì base có thể là bất kỳ số nào bắt đầu từ 5454 trở lên (vì mã ASCII của kí tự 5 là 5353).

Ý tưởng chính của thuật toán sẽ bắt đầu từ đây: Vì chuỗi kí tự ban đầu đã được mã hóa sang hệ cơ số base, ta sẽ tính giá trị thập phân của mã hóa này theo những kiến thức về hệ cơ số. Dễ nhận thấy rằng, nếu hai chuỗi có chung giá trị thập phân sau khi mã hóa thì chúng sẽ bằng nhau. Nhưng bạn đọc có lẽ cũng nhận ra, chuỗi kí tự có thể rất dài và việc mã hóa rồi tính giá trị thập phân của nó sẽ dẫn đến một giá trị quá lớn, không thể lưu trữ được bằng kiểu số nguyên thông thường trong máy tính.

Giải pháp là gì? Thay vì tính toàn bộ giá trị thập phân của dãy ra thì ta sẽ tính giá tri thập phân đó khi chia lấy dư cho một số nguyên MODMOD đủ lớn. Nói cách khác, nếu gọi xx là giá trị thập phân của mã hóa xâu aa và yy là giá trị thập phân của mã hóa xâu b,b, thì ta sẽ coi rằng a=ba = b nếu như x mod MOD=y mod MODx \text{ mod } MOD = y \text{ mod } MOD. Thực ra, theo toán học thì không có lý thuyết nào như vậy cả, tuy nhiên trong giải thuật Rolling Hash, chúng ta sẽ chấp nhận sai số của thuật toán và công nhận lập luận là đúng. Tỉ lệ sai số của thuật toán sẽ được trình bày kĩ hơn ở phần sau.

2. So sánh hai chuỗi kí tự bằng mã Hash

2.1. Tính mã Hash của toàn bộ chuỗi

Để đơn giản, mình sẽ gọi giá trị thập phân của chuỗi sau khi mã hóa là mã Hash của chuỗi đó. Muốn tính mã Hash của một chuỗi s,s, ta sử dụng trực tiếp mã ASCII của kí tự đó và làm giống như tính giá trị thập phân của một số ở hệ cơ số basebase. Giả sử chuỗi mã hóa của ss có NN kí tự được đánh số từ phải qua trái (bắt đầu từ 11):

s=sNsN−1...s1s = s_{N}s_{N - 1}...s_1

thì mã Hash của nó sẽ tính theo công thức:

hash(s)=sN×baseN−1+sN−1×baseN−2+⋯+s2×base1+s1×base0 (1)\text{hash}(s) = s_N\times base^{N - 1} + s_{N - 1}\times base^{N - 2} + \cdots + s_2 \times base^1 + s_1\times base^0 \ (1)

Mặt khác, Quy tắc Horner cho ta biết rằng:

a0+a1x+a2x2+a3x3+⋯aNxNa_0 + a_1x + a_2x^2 + a_3x^3 + \cdots a_Nx^N

=a0+x.(a1+x.(a2+x.(a3+⋯+x.(aN−1+xaN))))= a_0 + x.\bigg(a_1 + x.\Big(a_2 + x.\big(a_3 + \cdots + x.(a_{N- 1} + xa_N)\big)\Big)\bigg)

Vậy chúng ta biến đối biểu thức 11 thành:

hash(s)=((((base.sN+sN−1).base+sN−2).base+sN−3).base+⋯+s2).base+s1\text{hash(s)} = \bigg(\Big(\big((base.s_N + s_{N - 1}).base + s_{N - 2}\big).base + s_{N - 3}\Big).base + \cdots + s_2\bigg).base + s_1

Tuy nhiên, trên thực tế khi lập trình, các kí tự trong chuỗi được đánh số thứ tự từ trái qua phải, nên chuỗi s1...is_{1...i} sẽ có mã Hash là:

hash(s1...i)=∑j=1isj×basei−j=(((1.s1+s2).base+s3).base+⋯+si−1).base+si\text{hash}(s_{1...i}) = \sum_{j = 1}^i s_j \times base^{i - j} = \Big(\big((1.s_1 + s_ 2).base + s_3\big).base + \cdots + s_{i - 1}\Big).base + s_i

=hash(s1...i−1)×base+si= \text{hash}(s_{1...i - 1}) \times base + s_i

Ngoài ra, như mình đã nói ở trên, giá trị Hash này có thể rất lớn, nên ý tưởng của giải thuật Rolling Hash là sẽ lấy mã Hash sau khi chia lấy dư cho một số nguyên dương MODMOD rất lớn nào đó. Các bạn đừng quên thao tác này! Còn về cách lựa chọn basebase và MOD,MOD, ở đây các bạn tạm thời hiểu rằng mình chọn base=311base = 311 và MOD=109+7,MOD = 10^9 + 7, lí do lựa chọn như vậy các bạn sẽ đọc ở phần III. Phân tích và đánh giá giải thuật nhé!

Cài đặt:

long long hash_value_of_string(string s, long long MOD) // Lưu ý rằng chuỗi s ở đây mình đánh số từ vị trí 1 cho dễ thao tác.
{
    s = ' ' + s; // Thêm một kí tự trống vào đầu chuỗi để khiến chuỗi bắt đầu từ vị trí 1. Thao tác này chỉ làm một lần thôi.
    long long hash = 0;

    for (int i = 1; i < s.size(); ++i)
	hash = (hash * base + (int)s[i])) % MOD;

    return hash;
}

2.2. Tính mã Hash của một chuỗi con

Để tính mã Hash của một chuỗi con trong chuỗi s,s, bước 11 ta phải xây dựng được hai mảng:

  • Mảng power[i]power[i]: Giá trị của basei mod Mbase^i \text{ mod } M. Ý nghĩa của mảng này sẽ được đề cập ngay bên dưới đây.
  • Mảng hash[i]hash[i]: Mã Hash của chuỗi con s1...is_{1...i}.

Cài đặt 1: Xây dựng hai mảng power[i]power[i] và hash[i]hash[i]:

void create_hash(string s, long long MOD)
{
    power[0] = 1;
    for (int i = 1; i < s.size(); ++i)
        power[i] = (power[i - 1] * base) % MOD;

    for (int i = 1; i < s.size(); ++i)
	hash[i] = (hash[i - 1] * base + (int)s[i]) % MOD;
}

Giờ, muốn tính mã Hash của một chuỗi con sl...r,s_{l...r}, ta sử dụng công thức sau:

hash(sl...r)=hash(s1...r)−hash(s1...l−1)×baser−l+1 (2)\text{hash}(s_{l...r}) = \text{hash}(s_{1...r}) - \text{hash}(s_{1...l - 1}) \times base^{r - l + 1} \ (2)

Lí do tại sao hash(s1...l−1)\text{hash}(s_{1...l - 1}) lại phải nhân thêm với baser−l+1?base^{r - l + 1}? Lí do là vì, các mã Hash là giá trị của mã hóa xâu ss ở một hệ cơ số base,base, nghĩa là các đoạn con s1...l,s1...rs_{1...l}, s_{1...r} và sl...rs_{l...r} sẽ được đánh số như sau ở dạng hệ cơ số (và mã Hash của chúng cũng cần phải tính theo cách đánh số này):



Nhìn vào ba hình vẽ trên, có lẽ các bạn cũng đã tưởng tượng ra lí do rồi đúng không nào? Để lấy được giá trị Hash của đoạn sl...r,s_{l...r}, chúng ta cần đưa được về tính biểu thức:

∑i=1rsi×baser−i−∑i=1l−1si×baser−i\sum_{i = 1}^r s_i \times base^{r - i} - \sum_{i = 1}^{l - 1} s_i \times base^{r - i}

Nhưng chúng ta đang có mã Hash của đoạn s1...l−1s_{1...l - 1} và s1...rs_{1...r} thôi, vì vậy muốn tìm được (∑i=1l−1si×baser−i)\left(\sum_{i = 1}^{l - 1} s_i \times base^{r - i} \right) thì cần lấy mã Hash của đoạn này nhân thêm với baser−l+1base^{r - l + 1}. Và đó là cơ sở của công thức (2)(2). Ngoài ra, do trong công thức có phép trừ được thực hiện trên lớp đồng dư theo modulo MOD,MOD, nên kết quả có thể bị âm. Đối với những ngôn ngữ như C++, việc lấy số dư của một số âm khi chia cho một số khác có thể làm cho kết quả bị sai, vì thế ta cần làm dương kết quả đó lên bằng cách cộng thêm vào hiệu một giá trị MOD2MOD^2.

Cài đặt 2: Lấy mã Hash của một chuỗi con từ ll tới rr:

long long get_hash(int l, int r, long long MOD)
{
    return (hash[r] - hash[l - 1] * power[r - l + 1] + MOD * MOD) % MOD;
}

2.3. So khớp các chuỗi với nhau

Trở lại bài toán ban đầu, khi mà ở mỗi truy vấn, chúng ta cần so sánh chuỗi con Ai...i+M−1A_{i...i + M - 1} với chuỗi BB xem chúng có bằng nhau hay không. Với giải thuật Rolling Hash, sử dụng những gì đã phân tích ở trên, các bạn hoàn toàn làm được điều này chỉ trong O(1)!O(1)! Tất cả những gì chúng ta cần làm là lấy mã Hash của hai chuỗi này, xem chúng có bằng nhau hay không và đưa ra kết quả. Dưới đây là cài đặt hoàn chỉnh của cả chương trình cho bài toán ở phần I. Các bạn có thể thử nộp bài này trên đường link: https://oj.vnoi.info/problem/substr.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;
const long long base = 311, MOD = 1e9 + 7; // Chọn giá trị MOD = 10^9 + 7 và base = 311.
long long hash_b, power[maxn], hash_a[maxn];

void create_hash_function(string &a, string &b) // Khởi tạo các mảng cần thiết trong giải thuật.
{
     // Thêm dấu cách vào đầu chuỗi để khiến cho các kí tự bắt đầu từ vị trí 1. 
    a = ' ' + a; 
    b = ' ' + b;

    // Tạo các mảng power[i] và hash_a[i] là mã Hash tiền tố của chuỗi A.
    // Tính hash_b là mã Hash của toàn bộ chuỗi B.
    for (int i = 1; i < a.size(); ++i)
        power[i] = (power[i - 1] * base) % MOD;
    for (int i = 1; i < a.size(); ++i)
        hash_a[i] = hash_a[i - 1] * base + (long long)s[i];
    for (int i = 1; i < b.size(); ++b)
	hash_b = (hash_b * base + (long long)b[i]) % MOD;
 }

long long get_hash(int l, int r) // Lấy mã hash của một đoạn con [l...r] trên chuỗi A.
{
    return (hash_a[r] - hash_b[l - 1] * power[r - l + 1] + MOD * MOD) % MOD;
}

void solution(string a, string b)
{
    int N = a.size() - 1, M = b.size() - 1, res = 0;
    for (int i = 1; i <= N - M + 1; ++i)
        if (get_hash(i, i + M - 1) == hash_b)
	    ++res;
    
    cout << res; // Số lần xuất hiện của chuỗi B trong chuỗi A.
}

int main()
{
    string a, b; 
    cin >> a >>  b; // Nhập vào hai chuỗi kí tự ban đầu.
   
    create_hash_function(a, b); // Chuẩn bị dữ liệu.
    solution(a, b); // Giải quyết bài toán.
}

III. Phân tích và đánh giá giải thuật

1. Tính hiệu quả

Mặc dù bước chuẩn bị dữ liệu của giải thuật này sẽ mất độ phức tạp O(N),O(N), tuy nhiên điều quan trọng là chúng ta có thể so khớp hai chuỗi bất kỳ chỉ trong O(1)O(1) - rất nhanh phải không nào! Ngoài ra, nếu như đem so sánh cùng các giải thuật khác, Rolling Hash thực sự vô cùng dễ cài đặt. Điều này khiến cho nó được sử dụng rất thường xuyên trong các kỳ thi lập trình.

2. Tính chính xác

Có hai yếu tố chính trong giải thuật Rolling Hash là hệ cơ số basebase và modulo MODMOD.

Việc chứng minh tính chính xác của giải thuật này là khá phức tạp, mình sẽ để link ở đây cho bạn nào muốn tìm hiểu kĩ thêm. Còn trong bài viết này, chúng ta chỉ cần biết rằng, xác suất xảy ra kết quả sai của giải thuật là vô cùng nhỏ. Nhắc lại ý tưởng của giải thuật, chúng ta đang đánh giá hai giá trị aa và bb có bằng nhau hay không bằng một nhận định sai lầm:

a=b⇔a mod MOD=b mod MODa = b \Leftrightarrow a \text{ mod } MOD = b \text{ mod } MOD

Để giảm thiểu xác suất xảy ra sai số chỉ còn là 1MOD,\frac{1}{MOD}, các bạn cần lựa chọn basebase và MODMOD thỏa mãn đồng thời hai điều kiện sau:

  • MODMOD là số nguyên tố, thông thường chọn MOD≈109MOD \approx 10^9 trở lên là đạt được độ chính xác an toàn.
  • basebase là số nguyên tố lớn hơn mã ASCII của mọi kí tự trong chuỗi ss. Vì trong bảng mã ASCII có 255255 kí tự, nên mình thường chọn luôn base=311base = 311 để dù cho đề bài có cho xâu ss gồm những kí tự gì đi chăng nữa thì giải thuật vẫn bao quát được hết (thường thì trong các kỳ thi chúng ta chỉ quan tâm tới các kí tự chữ cái và chữ số thôi).

Một lưu ý nhỏ, các bạn chỉ được sử dụng giải thuật này để so khớp hai chuỗi có độ dài bằng nhau. Hiển nhiên hai chuỗi có độ dài khác nhau sẽ không bao giờ bằng nhau, nên không cần quan tâm trường hợp này để tránh sai sót không đáng có khi lập trình.

3. Tăng cường tính chính xác của giải thuật

Cùng xét một ví dụ sau:

"Cho chuỗi kí tự ss gồm N (1≤N≤105)N \ (1 \le N \le 10^5) kí tự và M (1≤M≤105)M \ (1 \le M \le 10^5) truy vấn khác nhau. Với mỗi truy vấn, cần kiểm tra xem hai đoạn con độ dài KK bắt đầu ở vị trí l1l_1 và l2l_2 của chuỗi ss có bằng nhau hay không?"

Với giải thuật Rolling Hash, chúng ta dễ dàng giải quyết bài toán này trong thời gian O(N+M)O(N + M). Mình sẽ không cài đặt lại, mà chỉ phân tích một chút về tính chính xác của giải thuật:

  • Tỉ lệ sai của giải thuật Hash dẫn đến từ việc có thể tồn tại hai chuỗi con khác nhau nhưng lại có chung mã Hash (bởi vì mọi chuỗi đều sẽ có mã Hash trong đoạn [0,MOD−1][0,MOD - 1]). Xác suất để xảy ra trường hợp hai chuỗi khác nhau mà có chung một mã Hash là xấp xỉ 1MOD→\frac{1}{MOD} \rightarrow xác suất để trả lời đúng một truy vấn là 1−1MOD1 - \frac{1}{MOD}. Với M=105,M = 10^5, và hãy giả sử bộ testcases của chúng ta gồm 100100 testcases. Khi đó, xác suất để trả lời đúng mọi truy vấn của tất cả các testcases là:

(1−1MOD)M×100≈0.9900 (MOD=109+7)\left(1 - \frac{1}{MOD}\right)^{M \times 100} \approx 0.9900 \ (MOD = 10^9 + 7) Xác suất này đủ để giúp chúng ta yên tâm pass qua tất cả các testcases.

  • Tuy nhiên, không phải là không có ngoại lệ. Dựa trên bài toán xác suất khá nổi tiếng là Nghịch lý ngày sinh, nếu như testcasess được sinh theo cách khiến cho số lượng chuỗi con khác nhau trong chuỗi càng nhiều, thì xác suất xảy ra trường hợp hai chuỗi khác nhau có cùng mã Hash sẽ ngày càng tăng lên. Cụ thể, nếu như N=30000,N = 30000, thì xác suất để tất cả các chuỗi con đều có mã Hash khác nhau là:

P(N)=(1−1MOD).(1−2MOD).(1−3MOD)...(1−NMOD)P(N) = \left(1 - \frac{1}{MOD}\right).\left(1 - \frac{2}{MOD}\right).\left(1 - \frac{3}{MOD}\right)...\left(1 - \frac{N}{MOD}\right)

Với MOD=109+7,MOD = 10^9 + 7, xác suất trên là khoảng 0.6376,0.6376, nghĩa là xác suất tồn tại hai chuỗi con khác nhau có cùng mã Hash lên tới 0.4,0.4, đồng nghĩa với việc khả năng trả lời sai testcases của bạn cũng tăng lên như vậy. Nói đơn giản thì, nếu như các bạn sử dụng duy nhất một giá trị MODMOD và basebase những người sinh test sẽ tìm cách bẫy bạn bằng cách tạo ra nhiều chuỗi con có cùng mã Hash. Để giải quyết việc này, chúng ta cần phải sử dụng nhiều MODMOD và nhiều basebase khác nhau. Lời khuyên của mình là sử dụng tối đa 1010 giá trị MODMOD và 1010 giá trị basebase khác nhau, vì nếu như sử dụng quá nhiều MODMOD và basebase cũng sẽ khiến cho chương trình chạy chậm đi.

IV. Vài bài toán ví dụ

1. Xử lý xâu - VOSTR

Link bài tập gốc: https://oj.vnoi.info/problem/vostr.

Tóm tắt đề bài: Cho hai chuỗi kí tự AA gồm MM kí tự và BB gồm NN kí tự (M,N≤106)(M, N \le 10^6) và QQ truy vấn (Q≤106)(Q \le 10^6). Với mỗi truy vấn, cần so sánh thứ tự từ điển của hai chuỗi con Al1...r1A_{l_1...r_1} và Bl2...r2?B_{l_2...r_2}?

Ý tưởng:

  • Tạo mã Hash tiền tố cho cả hai chuỗi AA và BB.
  • Ứng với mỗi truy vấn, ta cần so sánh thứ tự từ điển của hai chuỗi Al1...r1A_{l_1...r_1} và Bl2...r2B_{l_2...r_2}. Mà ta biết rằng, thứ tự từ điển của hai chuỗi sẽ phụ thuộc vào kí tự đầu tiên khác nhau giữa chúng. Vì thế, ta tìm kiếm nhị phân vị trí lmaxlmax lớn nhất sao cho chuỗi con Al1...l1+lmax−1=Bl2...l2+lmax−1A_{l_1...l_1 + lmax - 1} = B_{l_2...l_2 + lmax - 1}. Việc so sánh bằng nhau có thể thực hiện bằng giải thuật Rolling Hash. Lưu ý trước tiên ta kiểm tra xem độ dài và mã Hash của hai chuỗi có giống nhau hay không, nếu có thì kết luận luôn hai chuỗi bằng nhau.
  • Hai kí tự đầu tiên khác nhau giữa hai chuỗi sẽ là Al1+lmaxA_{l_1 + lmax} và Bl2+lmaxB_{l_2 + lmax}. Thứ tự từ điển giữa hai chuỗi sẽ phụ thuộc vào thứ tự từ điển của hai kí tự này (lớn hơn, nhỏ hơn).

Cài đặt:

#include <bits/stdc++.h>
#define task "HandleStr."
#define ff(i, a, b) for (int i = a; i <= (int) b; ++i)
#define fd(i, a, b) for (int i = a; i >= (int) b; --i)
#define rep(i, a, b) for (int i = a; i < (int) b; ++i)
#define inf 1e9 + 7
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair < int, int > II;
typedef pair < ll, ll > PLL;
typedef pair < double, int > DI;

const int maxn = 1e6 + 10, base = 31;
const long long mod = 1e9 + 7;
const int dd[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int m, n, ntest;
char a[maxn], b[maxn];
long long hasha[maxn], hashb[maxn], power[maxn];

void enter()
{
    freopen(task"inp", "r", stdin);
    freopen(task"out", "w", stdout);
    ios_base::sync_with_stdio(false);
    scanf("%d%d", &m, &n);
    scanf("%s\n", a + 1); 
    scanf("%s\n", b + 1);
    scanf("%d", &ntest);
}

// Tạo mã Hash tiền tố cho hai chuỗi.
void create()
{
    power[0] = 1;
    for (int i = 1; i <= max(m, n); ++i)
	power[i] = (power[i - 1] * base) % mod;
    for (int i = 1; i <= m; ++i)
	hasha[i] = (hasha[i - 1] * base + a[i] - 'a') % mod;
    for (int i = 1; i <= n; ++i) 
	hashb[i] = (hashb[i - 1] * base + b[i] - 'a') % mod;
}

long long get_hash(int l, int r, long long h[])
{
    return (h[r] - h[l - 1] * power[r - l + 1] + mod * mod) % mod;
}

// So khớp hai chuỗi bằng giải thuật tìm kiếm nhị phân: Tìm kiếm đoạn dài nhất bằng nhau giữa hai chuỗi.
char solve(int l, int r, int u, int v)
{
    if ((r - l) == (v - u) && get_hash(l, r, hasha) == get_hash(u, v, hashb))
        return '=';

    int length = min((r - l + 1), (v - u + 1));
    int left = 0, right = length, tmp = 0;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        ll t1 = get_hash(l, l + mid - 1, hasha);
        ll t2 = get_hash(u, u + mid - 1, hashb);
        if (t1 == t2)
        {
            left = mid + 1;
            tmp = mid;
        }
        else
            right = mid - 1;
    }

    if (tmp == length)
    {
        if ((r - l + 1) > length) return '>';
        if ((v - u + 1) > length) return '<';
    }

    int t1 = a[l + tmp] - 'a', t2 = b[u + tmp] - 'a';
    char ans = (t1 > t2) ? '>' : '<';

    return ans;
}

int main()
{
    enter();
    create();

    // Tính toán kết quả của các truy vấn, lưu các kết quả vào một vector.
    vector < char > res;
    int l, r, u, v;
    while (ntest--)
    {
        scanf("%d%d%d%d", &l, &r, &u, &v);
        res.push_back(solve(l, r, u, v));
    }

    for (char c: res)
        printf("%c\n", res[i]);

    return 0;
}

2. Chuỗi con xuất hiện KK lần - DKTSUB

Link bài tập gốc: https://oj.vnoi.info/problem/dtksub.

Tóm tắt đề bài: Cho chuỗi kí tự SS độ dài N,N, cần tìm độ dài của chuỗi con dài nhất xuát hiện ở KK vị trí khác nhau trong xâu S?S?

Ý tưởng:

  • Giả sử tồn tại một chuỗi con độ dài LL xuất hiện tối thiểu KK lần trong chuỗi S,S, thì chắc chắn cũng tồn tại các chuỗi con độ dài {1,2,3,...,L−1}\{1, 2, 3,..., L - 1\} xuất hiện tối thiểu KK lần trong chuỗi SS. Vì thế, ý tưởng ở đây là tìm kiếm nhị phân độ dài LL lớn nhất.
  • Ứng với mỗi độ dài L,L, ta tính mã Hash của mọi chuỗi con độ dài LL trong chuỗi SS ban đầu và sử dụng cấu trúc dữ liệu map để đếm số lần xuất hiện của các mã Hash đó. Nếu tồn tại mã Hash nào xuất hiện ít nhất KK lần thì kết luận độ dài LL này thỏa mãn và tăng LL lên bằng tìm kiếm nhị phân, ngược lại giảm LL xuống.
  • Để cho an toàn, cài đặt dưới đây mình sử dụng một giá trị basebase nhưng ba giá trị MODMOD khác nhau.

Cài đặt:

#include <bits/stdc++.h>
#define int long long
#define task "kstring."
#define inf 1e9 + 7
#define x first
#define y second

using namespace std;
const int mod[3] = {(int)1e9 + 2277, (int)1e9 + 5277, (int)1e9 + 8277}, base = 311;
const int maxn = 1e5 + 10;

int power[maxn][3], hash_code[maxn][3];

// Khởi tạo mã hash của chuỗi ban đầu.
void create_hash_table(string &s)
{
    // Thêm dấu cách vào đầu chuỗi để các kí tự bắt đầu từ vị trí 1 -> thuận tiện cho việc lấy mã hash một chuỗi con.
    s = ' ' + s;
    int N = s.size() - 1;

    // Khởi tạo bảng power[i][j]: Giá trị base^i % mod[j]. Sử dụng ba modulo để tăng tính chính xác cho giải thuật.
    power[0][0] = power[0][1] = power[0][2] = 1;
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j <= 2; ++j)
            power[i][j] = (power[i - 1][j] * base) % mod[j];

    // Tạo mã hash của xâu ban đầu theo chiều từ trái qua phải và từ phải qua trái.
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j <= 2; ++j)
            hash_code[i][j] = (hash_code[i - 1][j] * base + (int)s[i]) % mod[j];
}

// Lấy mã băm của một đoạn [l, r] trên chuỗi theo modulo thứ j, chiều từ trái qua phải.
int get_hash(int l, int r, int j)
{
    return (hash_code[r][j] - hash_code[l - 1][j] * power[r - l + 1][j] + mod[j] * mod[j]) % mod[j];
}

// Kiểm tra xem có tồn tại chuỗi con độ dài cur_length xuất hiện tối thiểu K lần trong chuỗi s hay không?
bool check_appear(string s, int cur_length, int K)
{
    int N = s.size() - 1;
    bool check = true;

    // Xét cả 3 giá trị MOD để xem kết quả có giống nhau không.
    for (int j = 0; j <= 2; ++j)
    {
        bool cur_check = false;
        unordered_map < int, int > mark;

        for (int i = 1; i <= N - cur_length + 1; ++i)
        {
            int code = get_hash(i, i + cur_length - 1, j);
            ++mark[code];

            if (mark[code] >= K)
            {
                cur_check = true;
                break;
            }
        }

        check &= cur_check;
    }

    return check;
}

void solution(string s, int K)
{
    // Tìm kiếm nhị phân độ dài của chuỗi dài nhất xuất hiện tối thiểu K lần.
    int max_length = 0, l = 0, r = s.size() - 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;

        if (check_appear(s, mid, K))
        {
            max_length = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }

    cout << max_length;
}

main()
{
    //freopen(task"inp", "r", stdin);
    //freopen(task"out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int N, K;
    cin >> N >> K;

    string s;
    cin >> s;

    create_hash_table(s);
    solution(s, K);

    return 0;
}

V. Tài liệu tham khảo

©️ Tác giả: Vũ Quế Lâm từ Viblo

Algorithm Viblo

All rights reserved

Mục lục


Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí