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