문자열 s가 있다고 가정하면 s의 가장 긴 접두사를 찾아야 하며, 이는 접미사이기도 합니다(자체 제외). 그러한 접두사가 없으면 단순히 빈 문자열을 반환합니다.
따라서 입력이 "madam"과 같으면 출력은 "m"이 되고 자신을 제외한 4개의 접두사가 있습니다. 이들은 "m", "ma", "mad", "mada" 및 "m", "am", "dam", "adam"과 같은 4개의 접미사입니다. 접미사이기도 한 가장 큰 접두사는 "m"으로 지정됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
lps() 함수를 정의하면 s가 걸립니다.
-
n :=s
의 크기 -
n
크기의 배열 ret 정의 -
j :=0, i :=1
-
나는
-
s[i]가 s[j]와 같으면 -
-
ret[i] :=j + 1
-
(i를 1씩 증가)
-
(j를 1씩 증가)
-
-
그렇지 않으면 s[i]가 s[j]와 같지 않으면 -
-
j> 0이면 -
-
j :=ret[j − 1]
-
-
그렇지 않으면
-
(i를 1씩 증가)
-
-
-
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
n :=s
의 크기 -
n이 1과 같으면 -
-
빈 문자열 반환
-
-
배열 정의 v =lps(s)
-
x :=v[n − 1]
-
ret :=빈 문자열
-
initialize i :=0의 경우, i
-
렛 :=렛 + s[i]
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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"));
} 입력
"helloworldhello"
출력
hello