Hướng dẫn giải của Khớp xâu
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for khopxau: Khớp xâu
Hiểu bài toán
Cho hai xâu ký tự s và t (chỉ gồm chữ cái thường, độ dài t <= độ dài s). Tìm tất cả các vị trí i (tính từ 1) trong xâu s sao cho xâu t xuất hiện bắt đầu tại i (tức là s[i..i+|t|-1] = t). Đây là bài toán tìm tất cả các lần xuất hiện của một xâu trong xâu khác (Multiple Pattern Matching). Với độ dài lên tới 10^6, giải thuật tìm kiếm thông thường (O(n*m)) sẽ quá chậm, cần sử dụng các thuật toán tối ưu hơn.
Các cách tiếp cận
Cách Brute Force (Naive String Matching)
#include <stdio.h>
#include <string.h>
#define MAXN 1000005
char s[MAXN], t[MAXN];
int main() {
scanf("%s %s", s, t);
int n = strlen(s);
int m = strlen(t);
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (s[i + j] != t[j]) break;
}
if (j == m) {
printf("%d ", i + 1);
}
}
return 0;
}
- Time Complexity: O(n * m)
- Space Complexity: O(1)
Giải thuật này sử dụng 2 vòng lặp lồng nhau. Vòng lặp ngoài duyệt qua từng vị trí i trong xâu s (từ 0 đến n-m). Vòng lặp trong kiểm tra xem xâu t có khớp với xâu s bắt đầu từ i hay không bằng cách so sánh từng ký tự. Nếu khớp hết thì in ra vị trí i+1. Với n, m lên tới 10^6, độ phức tạp O(n*m) sẽ thực hiện khoảng 10^12 phép tính, quá chậm so với giới hạn thời gian (thường là 1-2 giây).
Cách KMP (Knuth-Morris-Pratt)
#include <stdio.h>
#include <string.h>
#define MAXN 1000005
char s[MAXN], t[MAXN];
int lps[MAXN]; // Longest Prefix Suffix
void computeLPSArray(char *pat, int M, int *lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
void KMPSearch(char *pat, char *txt) {
int M = strlen(pat);
int N = strlen(txt);
computeLPSArray(pat, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
printf("%d ", i - j + 1);
j = lps[j - 1];
} else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
int main() {
scanf("%s %s", s, t);
// Lưu ý: Trong code mẫu, s là text, t là pattern
// Đầu vào: s là text, t là pattern
KMPSearch(t, s);
return 0;
}
// Code mẫu tham khảo từ submission 1476018
- Time Complexity: O(n + m)
- Space Complexity: O(m)
Thuật toán KMP tối ưu hóa việc so sánh bằng cách sử dụng cấu trúc tiền tố chung dài nhất (LPS array) của pattern t.
- Xây dựng LPS: Mảng lps[i] lưu độ dài tiền tố dài nhất của t[0..i] cũng là hậu tố của t[0..i]. Việc này giúp biết được khi mismatch, ta có thể bỏ qua bao nhiêu ký tự đã khớp.
- Tìm kiếm: Khi duyệt qua xâu s, nếu có sự không khớp (mismatch) ở vị trí j của pattern, thay vì lùi lại từ đầu, ta giữ nguyên chỉ số i của text và chỉ di chuyển j về vị trí lps[j-1]. Điều này đảm bảo mỗi ký tự trong text chỉ được xử lý tối đa 2 lần, đạt độ phức tạp O(n+m).
Cách Rabin-Karp (Rolling Hash)
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#define MAXN 1000005
char s[MAXN], t[MAXN];
int main() {
scanf("%s %s", s, t);
int n = strlen(s);
int m = strlen(t);
if (m > n) return 0;
// Parameters for Rolling Hash
const uint64_t B = 31; // Base
const uint64_t M = 1e9 + 7; // Modulo
// Precompute B^(m-1) % M
uint64_t h_b = 1;
for (int i = 0; i < m - 1; i++) {
h_b = (h_b * B) % M;
}
// Calculate hash of pattern t and first window of s
uint64_t h_t = 0;
uint64_t h_s = 0;
for (int i = 0; i < m; i++) {
h_t = (h_t * B + (t[i] - 'a' + 1)) % M;
h_s = (h_s * B + (s[i] - 'a' + 1)) % M;
}
// Slide window
for (int i = 0; i <= n - m; i++) {
if (h_s == h_t) {
// Check for collisions (optional but recommended for safety)
int match = 1;
for (int k = 0; k < m; k++) {
if (s[i + k] != t[k]) {
match = 0;
break;
}
}
if (match) {
printf("%d ", i + 1);
}
}
// Update hash for next window
if (i < n - m) {
h_s = (h_s - (s[i] - 'a' + 1) * h_b) % M;
if (h_s < 0) h_s += M;
h_s = (h_s * B + (s[i + m] - 'a' + 1)) % M;
}
}
return 0;
}
- Time Complexity: O(n + m) (trung bình)
- Space Complexity: O(1)
Sử dụng kỹ thuật Rolling Hash.
- Tính giá trị băm (hash) của xâu t.
- Tính giá trị băm của cửa sổ trượt đầu tiên trong s (có độ dài m).
- Duyệt qua s, so sánh hash của cửa sổ hiện tại với hash của t. Nếu bằng nhau, ta kiểm tra lại chắc chắn (tránh đụng độ hash) và in ra vị trí.
- Cập nhật hash cho cửa sổ tiếp theo trong thời gian O(1) bằng cách loại bỏ ký tự đầu tiên và thêm ký tự cuối cùng. Giải thuật này có độ phức tạp trung bình là O(n+m), nhưng trong trường hợp xấu nhất (nhiều đụng độ) có thể chậm hơn KMP.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n * m) | O(1) | Brute Force (Naive String Matching) |
| 2 | O(n + m) | O(m) | KMP (Knuth-Morris-Pratt) |
| 3 | O(n + m) (trung bình) | O(1) | Rabin-Karp (Rolling Hash) |
Bài học kinh nghiệm
- Bài toán này là bài toán kinh điển về xử lý xâu (String Matching).
- Với ràng buộc độ dài lớn (10^6), giải thuật O(n*m) không khả thi.
- KMP (Knuth-Morris-Pratt) là thuật toán chuẩn đảm bảo thời gian chạy O(n+m) trong mọi trường hợp.
- Rolling Hash là một lựa chọn khác với độ phức tạp trung bình O(n+m) và dễ cài đặt, nhưng cần cẩn thận với hiện tượng đụng độ (hash collision).
Lỗi thường gặp
- Quên xử lý chỉ số (thường là 1-based indexing cho output trong khi code sử dụng 0-based).
- Lỗi tràn số nguyên khi tính hash (nên dùng unsigned long long và modulo).
- Sai logic trong việc cập nhật chỉ số j trong KMP (j = lps[j-1] chứ không phải j = 0).
- Đọc sai thứ tự input (sau đó nhầm lẫn giữa text và pattern khi gọi hàm KMP).
- Xử lý input với fgets có thể lấy theo ký tự newline '\n', cần loại bỏ.
Bình luận