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("helloworldhello"));
}

入力

"helloworldhello"

出力

hello