假设我们有一个字符串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