Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

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"

출력

m