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