数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究C++ 中的最短回文
假设我们有一个字符串 s。我们可以通过在其前面添加字符来将其转换为回文。我们必须找到最短的回文，我们可以利用此信息找到。因此，如果该字符串为 “abcc”，那么结果将为 − "ccbabcc"。
为解决此问题，我们将按照以下步骤操作 −
n := s 的大小，s1 := s，s2 := s
反转字符串 s2
s2 := s 连接 "#" 连接 s2
定义一个与 s2 大小相同的数组 lps
j := 0，i := 1
当 i < s2 的大小时，执行 −
如果 s2[i] 与 s2[j] 相同，则
lps[i] := j + 1
将 i 加 1，将 j 加 1
否则
如果 j > 0，则 j := lps[j - 1]
否则将 i 加 1
extra := 从 lps[s 的大小 – 1] 到 n - lps[lps 的大小 - 1]) 的 s 的子字符串
反转 extra
返回 extra 连接 s
示例
为了更好地理解，让我们看下面的实现 −
#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
更新于: 2020 年 5 月 26 日
650 次浏览
广告