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

• i

  • s[i]がs[j]と同じ場合、

    • ret [i]：=j + 1

    • （iを1増やします）

    • （jを1増やします）

  • それ以外の場合、s[i]がs[j]と等しくない場合、-

    • j> 0の場合、-

      • j：=ret [j-1]

    • それ以外の場合

      • （iを1増やします）

• retを返す

• メインの方法から、次のようにします-

• n：=sのサイズ

• nが1と同じ場合、-

  • 空白の文字列を返す

• 配列を定義するv=lps（s）

• x：=v [n-1]

• ret：=空白の文字列

• 初期化i：=0の場合、i

  • ret：=ret + s [i]

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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