Để giải quyết vấn đề này, phép liệt kê thông thường sẽ không hiệu quả, bởi vì tiệm cận của nó sẽ là
O(t*s). Do đó, đối với các tác vụ tìm kiếm chuỗi con, thuật toán KMP (Knuth-Morris-Pratt) được sử dụng.
Để thực hiện thuật toán này, hàm tiền tố chuỗi được sử dụng, đây là một mảng các số có độ dài
n (strong>s độ dài), trong đó mỗi phần tử là độ dài tối đa của hậu tố riêng lớn nhất của chuỗi con
s, khớp với tiền tố của nó. Ví dụ:
| Dòng |
Hàm tiền tố |
Ghi chú |
| abababcab |
0 0 1 2 3 4 0 1 2 |
|
| abcabcd |
0 0 0 1 2 3 0 |
|
| aabaaab |
0 1 0 1 2 2 3 |
|
Thuật toán hàm tiền tố tầm thường với tiệm cận O(n^3):
vector<int> tiền tố_hàm (chuỗi s) {
int n = (int ) s.length();
vector<int>pi(n);
cho (int i=0; i<n; ++i)
cho (int k=0; k<=i; ++k)
if (s.substr(0,k) == s .substr(i-k+1,k))
pi[i] = k;
trả vềpi;
}
Và bây giờ chúng ta cần tạo một hàm tiền tố cho một chuỗi có dạng: t + # + s, trong đó # là ký tự phân cách rõ ràng không có trong văn bản. Phân tích các giá trị của hàm tiền tố sau ký tự phân cách tương ứng, cần lưu ý rằng nếu giá trị kết quả bằng độ dài của chuỗi con mong muốn, thì sự xuất hiện của nó sẽ được tìm thấy. Ví dụ: đối với chuỗi "abababcab" và chuỗi con mong muốn "abab", hàm tiền tố sẽ là:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 chúng ta cần phân tích cú pháp các phần tử của chuỗi tương ứng s:
1 2 3 4 3 4 0 1 2 - có hai trường hợp giá trị là 4 ( thứ 4 và thứ 6), tức là độ dài t, kết quả là câu trả lời phải được viết: 4 - 4 (độ dài t) & nbsp; = 0 và 6 - 4 = 2. Có thể thấy đây là đáp án đúng và chuỗi "abab" thực sự là một chuỗi con trong chuỗi "abababcab" ở vị trí 0 và 2.
Sau khi tối ưu hóa chức năng tiền tố (để biết chi tiết tại đây ), chúng tôi nhận được thuật toán cuối cùng với tiệm cận O(n):
vector<int> tiền tố_hàm (chuỗi s) {
int n = (int ) s.length();
vector<int>pi(n);
cho (int i=1; i<n; ++i) {
int j = pi[i-1< /span>];
trong khi (j > 0 && s[i] != s[j])
j = pi[j-1];
nếu (s[i] == s[j]) ++j;
pi[i] = j;
}
trả vềpi;
}
|
Z-chức năng
Z-function từ chuỗi S - mảng Z, mỗi phần tử của nó là Z [i ] bằng tiền tố dài nhất của chuỗi con bắt đầu từ vị trí i trong chuỗi S, cũng là tiền tố của toàn bộ chuỗi Z. Giá trị của hàm Z tại vị trí 0 thường bằng 0 hoặc bằng độ dài của toàn bộ chuỗi.
Khó khăn
O(|S| ^ 2) hoặc O(|S|).
Hàm tiền tố từ chuỗi S - mảng P, mỗi phần tử trong đó P[i] bằng với hậu tố dài nhất của chuỗi con bắt đầu từ vị trí < code>i trong chuỗi S, cũng là hậu tố của toàn bộ chuỗi S. Giá trị của hàm P tại vị trí 0 thường bằng 0 hoặc bằng độ dài của toàn bộ chuỗi.
Khó khăn
O(|S| ^ 2) hoặc O(|S|).
Thử triển khai hàm Z và hàm tiền tố cho O(|S| ^ 2) .
|
Cả Z và tiền tố hàm đều có thể được sử dụng để triển khai thuật toán KMP(Knuth-Morris-Pratt) để tìm một chuỗi con trong một chuỗi trong O(|S|). Bản chất của thuật toán này như sau: chúng tôi gán cho chuỗi mà chúng tôi muốn tìm chuỗi mà chúng tôi đang tìm kiếm. Bạn nên đặt một ký tự phân cách giữa các dòng này, tức là một ký tự không xuất hiện trong bất kỳ dòng nào (thường là #).
|