Module: Chức năng tiền tố, chức năng Z

Để 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ụ:
 

Thuật toán hàm tiền tố tầm thường với tiệm cận O(n^3):


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.

 

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

<đầu>

#	Đầu vào	Đầu ra
1	abababcab abab	0 2

Write the program below
#include <iostream> #include <vector> #include <string> using namespace std; vector<int> prefix_function(string s) { int n = (int)s.length(); vector<int> pi(n); for (int i = 0; i < n; ++i) for (int k = 0; k <= i; ++k) if (s.substr(0, k) == s.substr(i - k + 1, k)) pi[i] = k; return pi; } int main() { string s, t; cin >> s >> t; s = t + '#' + s; vector<int> pi; pi = prefix_function(s);
return 0; }