Giả sử chúng ta có một chuỗi s, chúng ta phải tìm tiền tố hạnh phúc dài nhất của s. Một chuỗi được gọi là tiền tố hạnh phúc nếu là một tiền tố không rỗng cũng là một hậu tố (không bao gồm chính nó). Nếu không có tiền tố happy 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("madam"));
} Đầu vào
"madam"
Đầu ra
m