C ++中最短的回文

假设我们有一个字符串s。我们可以通过在其前面添加字符来将其转换为回文。我们必须找到最短的回文,我们可以找到执行此信息的地方。因此,如果字符串类似于“ abcc”,则结果将为-“ ccbabcc”。

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

  • n:= s的大小,s1:= s,s2:= s

  • 反转字符串s2

  • s2:= s串联“#”串联s2

  • 定义大小与s2相同的数组lps

  • j:= 0,i:= 1

  • 当我<s2的大小时,做-

    • 如果j> 0,则j:= lps [j-1]

    • 否则我加1

    • lps [i]:= j + 1

    • 将i加1,将j加1

    • 如果s2 [i]与s2 [j]相同,则

    • 除此以外

    • 额外:= s的子串,从lps [s的大小– 1]到n-lps [lps的大小-1])

    • 反转额外

    • 返回额外的串联

    例 

    让我们看下面的实现以更好地理解-

    #include <bits/stdc++.h>
    using namespace std;
    class Solution {
       public:
       string shortestPalindrome(string s) {
          int n = s.size();
          string s1 = s;
          string s2 = s;
          reverse(s2.begin(), s2.end());
          s2 = s + "#" + s2;
          vector <int> lps(s2.size());
          int j = 0;
          int i = 1;
          while(i <s2.size()){
             if(s2[i] == s2[j]){
                lps[i] = j + 1;
                j++;
                i++;
             } else {
                if(j > 0){
                   j = lps[ j - 1];
                } else {
                   i++;
                }
             }
          }
          string extra = s.substr(lps[lps.size() - 1], n - lps[lps.size() - 1]);
          reverse(extra.begin(), extra.end());
          return extra + s;
       }
    };
    main(){
       Solution ob;
       cout << (ob.shortestPalindrome("abcc"));
    }

    输入值

    “abcc”

    输出结果

    ccbabcc