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