สมมติว่าเรามีสตริง s เราสามารถแปลงเป็นพาลินโดรมได้โดยการเพิ่มอักขระไว้ข้างหน้า เราต้องหา palindrome ที่สั้นที่สุด ที่เราจะหาข้อมูลนี้ได้ ดังนั้นหากสตริงเป็นเหมือน “abcc” ผลลัพธ์จะเป็น − "ccbabcc"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
n :=ขนาดของ s, s1 :=s, s2 :=s
-
ย้อนกลับสตริง s2
-
s2 :=s ต่อ "#" ต่อ s2
-
กำหนดอาร์เรย์ lps ที่มีขนาดเท่ากับ s2
-
เจ :=0, ผม :=1
-
ในขณะที่ฉัน <ขนาดของ s2 ทำ −
-
ถ้า s2[i] เหมือนกับ s2[j] แล้ว
-
lps[i] :=j + 1
-
เพิ่ม i 1, เพิ่ม j 1
-
-
มิฉะนั้น
-
ถ้า j> 0 แล้ว j :=lps[j - 1]
-
ไม่เช่นนั้นให้เพิ่ม i ขึ้น 1
-
-
-
พิเศษ :=สตริงย่อยของ s จาก lps[ขนาดของ s – 1] ถึง n - lps[ขนาดของ lps - 1])
-
ย้อนกลับพิเศษ
-
ส่งคืน concatenate พิเศษ 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
