Giả sử chúng ta có một chuỗi s, chúng ta phải tìm tiền tố dài nhất của s, tiền tố này cũng là một hậu tố (loại trừ chính nó). Nếu không có tiền tố như vậy, thì chỉ cần trả về chuỗi trống.
Vì vậy, nếu đầu vào là "madam", thì đầu ra sẽ là "m", nó có 4 tiền tố loại trừ chính nó. Đó là "m", "ma", "mad", "mada" và 4 hậu tố như "m", "am", "dam", "adam". Tiền tố lớn nhất cũng là hậu tố được đưa ra bởi "m".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm lps (), điều này sẽ mất s,
-
n:=kích thước của s
-
Xác định ret mảng có kích thước n
-
j:=0, i:=1
-
trong khi tôi
-
nếu s [i] giống với s [j] thì -
-
ret [i]:=j + 1
-
(tăng tôi lên 1)
-
(tăng j lên 1)
-
-
ngược lại khi s [i] không bằng s [j] thì -
-
nếu j> 0, thì -
-
j:=ret [j - 1]
-
-
Nếu không
-
(tăng tôi lên 1)
-
-
-
-
trả lại ret
-
Từ phương thức chính, thực hiện như sau -
-
n:=kích thước của s
-
nếu n giống 1 thì -
-
trả về chuỗi trống
-
-
Xác định một mảng v =lps (s)
-
x:=v [n - 1]
-
ret:=chuỗi trống
-
để khởi tạo i:=0, khi i
-
ret:=ret + s [i]
-
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector <int> lps(string s){
int n = s.size();
vector<int> ret(n);
int j = 0;
int i = 1;
while (i < n) {
if (s[i] == s[j]) {
ret[i] = j + 1;
i++;
j++;
}
else if (s[i] != s[j]) {
if (j > 0)
j = ret[j - 1];
else {
i++;
}
}
}
return ret;
}
string longestPrefix(string s) {
int n = s.size();
if (n == 1)
return "";
vector<int> v = lps(s);
int x = v[n - 1];
string ret = "";
for (int i = 0; i < x; i++) {
ret += s[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.longestPrefix("helloworldhello"));
} Đầu vào
"helloworldhello"
Đầu ra
hello