C++에서 가장 긴 해피 접두사

문자열 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("madam"));
}

입력

"madam"