C ++中最长的快乐前缀

假设我们有一个字符串s，我们必须找到s的最长快乐前缀。如果字符串是一个非空前缀，它也是一个后缀（不包括其后缀），则称为幸福前缀。如果没有这样的快乐前缀，则只需返回空白字符串。

因此，如果输入像“女士”，那么输出将是“ m”，它有4个前缀（不包括自身）。它们是“ m”，“ ma”，“ mad”，“ mada”和4个后缀，例如“ m”，“ am”，“ dam”，“ adam”。后缀的最大前缀由“ m”给出。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数lps()，它将花费s，

• n：= s的大小

• 定义大小为n的数组ret

• j：= 0，i：= 1

• 当我<n时，-

• 如果j> 0，则-

• 除此以外

• j：= ret [j-1]

• （将i增加1）

• ret [i]：= j + 1

• （将i增加1）

• （将j增加1）

• 如果s [i]与s [j]相同，则

• 否则，当s [i]不等于s [j]时，则-

• 返回ret

• 从主要方法中执行以下操作-

• n：= s的大小

• 如果n与1相同，则-

• 返回空白字符串

• 定义一个数组v = lps(s)

• x：= v [n-1]

• ret：=空字符串

• 对于初始化i：= 0，当i <x时，更新（将i增加1），执行-

• 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