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