資料結構
網路
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 次瀏覽
廣告