10.3K 776 120

Đã đăng vào thg 12 26, 2022 10:20 SA 18 phút đọc

2.2K

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ự $A$ độ dài $N \ (1 \le N \le 10^5)$ và một chuỗi kí tự $B$ độ dài $M \ (1 \le M \le 10^5)$ . Cần trả lời câu hỏi: Chuỗi kí tự $B$ xuất hiện bao nhiêu lần trong chuỗi kí tự $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 $M$ trong chuỗi $A,$ với mỗi chuỗi con ta so khớp nó với chuỗi $B$ . Giải thuật này có độ phức tạp $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 $1974$ . Giải thuật này có tính hiệu quả rất cao, độ phức tạp chỉ là $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ừ $0$ tới $255$ . 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\}$ .

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ừ $101$ 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ừ $54$ trở lên (vì mã ASCII của kí tự 5 là $53$ ).

Ý 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 $MOD$ đủ lớn. Nói cách khác, nếu gọi $x$ là giá trị thập phân của mã hóa xâu $a$ và $y$ là giá trị thập phân của mã hóa xâu $b,$ thì ta sẽ coi rằng $a = b$ nếu như $x \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,$ 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ố $base$ . Giả sử chuỗi mã hóa của $s$ có $N$ kí tự được đánh số từ phải qua trái (bắt đầu từ $1$ ):

$s = s_{N}s_{N - 1}...s_1$

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

$\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:

$a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots a_Nx^N$

$= 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 $1$ thành:

$\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 $s_{1...i}$ sẽ có mã Hash là:

$\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$

$= \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 $MOD$ 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 $base$ và $MOD,$ ở đây các bạn tạm thời hiểu rằng mình chọn $base = 311$ và $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,$ bước $1$ ta phải xây dựng được hai mảng:

Mảng $power[i]$ : Giá trị của $base^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]$ : Mã Hash của chuỗi con $s_{1...i}$ .

Cài đặt 1: Xây dựng hai mảng $power[i]$ và $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 $s_{l...r},$ ta sử dụng công thức sau:

$\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 $\text{hash}(s_{1...l - 1})$ lại phải nhân thêm với $base^{r - l + 1}?$ Lí do là vì, các mã Hash là giá trị của mã hóa xâu $s$ ở một hệ cơ số $base,$ nghĩa là các đoạn con $s_{1...l}, s_{1...r}$ và $s_{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 $s_{l...r},$ chúng ta cần đưa được về tính biểu thức:

$\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 $s_{1...l - 1}$ và $s_{1...r}$ thôi, vì vậy muốn tìm được $\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 $base^{r - l + 1}$ . Và đó là cơ sở của công thức $(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,$ 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ị $MOD^2$ .

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

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 $A_{i...i + M - 1}$ với chuỗi $B$ 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)!$ 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),$ 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)$ - 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ố $base$ và modulo $MOD$ .

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ị $a$ và $b$ có bằng nhau hay không bằng một nhận định sai lầm:

$a = 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à $\frac{1}{MOD},$ các bạn cần lựa chọn $base$ và $MOD$ thỏa mãn đồng thời hai điều kiện sau:

$MOD$ là số nguyên tố, thông thường chọn $MOD \approx 10^9$ trở lên là đạt được độ chính xác an toàn.
$base$ là số nguyên tố lớn hơn mã ASCII của mọi kí tự trong chuỗi $s$ . Vì trong bảng mã ASCII có $255$ kí tự, nên mình thường chọn luôn $base = 311$ để dù cho đề bài có cho xâu $s$ 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ự $s$ gồm $N \ (1 \le N \le 10^5)$ kí tự và $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 $K$ bắt đầu ở vị trí $l_1$ và $l_2$ của chuỗi $s$ 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)$ . 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]$ ). 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ỉ $\frac{1}{MOD} \rightarrow$ xác suất để trả lời đúng một truy vấn là $1 - \frac{1}{MOD}$ . Với $M = 10^5,$ và hãy giả sử bộ testcases của chúng ta gồm $100$ testcases. Khi đó, xác suất để trả lời đúng mọi truy vấn của tất cả các testcases là:

$\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,$ thì xác suất để tất cả các chuỗi con đều có mã Hash khác nhau là:

$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 = 10^9 + 7,$ xác suất trên là khoảng $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,$ đồ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ị $MOD$ và $base$ 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 $MOD$ và nhiều $base$ khác nhau. Lời khuyên của mình là sử dụng tối đa $10$ giá trị $MOD$ và $10$ giá trị $base$ khác nhau, vì nếu như sử dụng quá nhiều $MOD$ và $base$ 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ự $A$ gồm $M$ kí tự và $B$ gồm $N$ kí tự $(M, N \le 10^6)$ và $Q$ truy vấn $(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 $A_{l_1...r_1}$ và $B_{l_2...r_2}?$

Ý tưởng:

Tạo mã Hash tiền tố cho cả hai chuỗi $A$ và $B$ .
Ứng với mỗi truy vấn, ta cần so sánh thứ tự từ điển của hai chuỗi $A_{l_1...r_1}$ và $B_{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í $lmax$ lớn nhất sao cho chuỗi con $A_{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à $A_{l_1 + lmax}$ và $B_{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 $K$ 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ự $S$ độ dài $N,$ cần tìm độ dài của chuỗi con dài nhất xuát hiện ở $K$ vị trí khác nhau trong xâu $S?$

Ý tưởng:

Giả sử tồn tại một chuỗi con độ dài $L$ xuất hiện tối thiểu $K$ lần trong chuỗi $S,$ thì chắc chắn cũng tồn tại các chuỗi con độ dài $\{1, 2, 3,..., L - 1\}$ xuất hiện tối thiểu $K$ lần trong chuỗi $S$ . Vì thế, ý tưởng ở đây là tìm kiếm nhị phân độ dài $L$ lớn nhất.
Ứng với mỗi độ dài $L,$ ta tính mã Hash của mọi chuỗi con độ dài $L$ trong chuỗi $S$ 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 $K$ lần thì kết luận độ dài $L$ này thỏa mãn và tăng $L$ lên bằng tìm kiếm nhị phân, ngược lại giảm $L$ xuống.
Để cho an toàn, cài đặt dưới đây mình sử dụng một giá trị $base$ nhưng ba giá trị $MOD$ 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;
}