大家好,又见面了,我是你们的朋友全栈君。
前言
回文字符串,就是像“12321”这种轴对称形式的字符串。
但并不是所有的字符串都是这种整个串都是回文串的,比如1232。有些计算机问题就是在一个字符串中找出一段最长的回文字符子串,这个时候时候,我们就需要一些算法来求出结构。
方法一:暴力求解
char str[10]={
"5234331"};
int len=strlen(str),max=0;
for(int i=0;i<len;i++){
int res=1,j=1;
while(i-j>=0&&i+j<len-1&&str[i-j]==str[i+j]) {
res+=2;j++;}
if(res>max) max=res;
}
printf("%d",max);
这种做法就是对每一个字符,匹配它左右两边的字符,如果相同,则res+=2,最后取最大值max。
时间复杂度达到了O(n2),当字符长度到10000时,程序的效率就不行了,时间复杂度太高。
而且这种方法还要判断长度的奇偶性(上面只是判断奇数,在这里就不多说了),代码比较长。
方法二:Manacher算法
时间复杂度由O(n2)缩短为O(n),运行效率提高了很多(tql)。
1. 变换
既然回文字符串有奇偶之分,分奇偶的话,程序将会很复杂,那么我们就要想办法避免这种情况。随便选两个不同的字符串,比如”123324″,“123432”,这两个字符串的最长回文子串奇偶性都不同。那么我们选一个字符串中没出现的字符(如#),将其插入到上面的字符串每个字符的左右两边,变成如下形式
#1#2#3#3#2#4#
#1#2#3#2#3#2#
这样回文子串长度都变成了奇数,有利于计算(舒服)。
处理一个字符串S之后,我们在利用一个和S等长的数组L,其中L[ i ]表示以S[ i ]为中心的回文串的半径,如下:
212321
# 2 # 1 # 2 # 3 # 2 # 1 #
1 2 1 4 1 2 1 6 1 4 1 2 1
仔细观察上面的式子,发现以‘3’为中心的回文串半径为6,而对应的回文串“12321”长度为5,以‘1’为中心的回文串的半径为4,而对应的回文串“212”长度为3,规律很快就找到了:回文串的长度等于半径-1。所以我们只需要找出最大的半径就可以找出最长的回文串的长度。但是如果想要定位最长回文子串的位置,我们还需要知道字符串的起始位置。
我们来看“12321”这个回文子串,它的中间字符‘3’在改变后的字符串中的位置为7,它的半径为6,7-6=1,这样发现,字符串“12321”在原字符串中的位置就是1。再来看“212”这个字符串,他的中间字符位置和半径分别为3和4,但是3-4=-1,起始位置变成负数了,这样是不行的。所以我们这时在字符串的首位添加一个特殊的字符。
比如‘&’,字符串变成:
& # 2 # 1 # 2 # 3 # 2 # 1 #
1 1 2 1 4 1 2 1 6 1 4 1 2 1
(下标从零开始)
这样做仅仅只是把字符串往后移一位,没有做出过多改变,但是带来的收益却很大。
再来看“212”这个字符串,它的中间字符位置变为,4,半径为4,这样一减等于0,没有出现负数,而且在原字符串中的起始位置也为0,感觉可以,再来看“12321”,它的中间字符位置变为8,半径为6,一减等于2,除以2等于1,它在原字符串中的起始位置也为1,这样和上面的例子结合起来,发现添加‘&’后:
( 中间字符的位置-半径 ) / 2=在原字符串中的起始位置
由上面的推导,我们得出算法的规律,现在就差代码实现了。
2. 计算
现在需要的就是如何求出半径数组L[ i ]。设id和mx分别为最接近字符尾的回文子串的中点位置和右端位置。那么整个核心算法如下:
L[i]=mx>i?min(L[2*id-i],mx-i):1;
当mx>i,则L[ i ]=min( L[2 * id – i] , mx-i),否则L[ i ]=1。
如上图:
- 当mx-i>L[ j ]的时候,以S[ id ]为中心的回文子串包含以S[ j ]为中心的回文子串,由于 i 和 j 对称且id左右两边对称,所以以S[ id ]为中心的回文子串必然也包含以S[ j ]为中心的回文子串,见上图,所以有L[ i ]=L[ j ],其中 j = id * 2-i 。
- 当mx-i<L[ j ]的时候,以S[ id ]为中心的回文子串不一定完全包含以S[ j ]为中心的回文子串,但由于对称性可知,L[ i ]和L[ j ]在绿线以内的部分是相同的,但是到mx之外的部分需要额外取匹配
- 当i>mx时,因为i已经超过mx了,所以找不到对称点,只能额外匹配了。
通过上面的过程可以得出一个最长回文子串,下面给出代码
#include<bits/stdc++.h>
using namespace std;
int main(){
string s,t("!#");
getline(cin,s);
//将s化成 !#a#b#c#b#c 这种形式
//其目的是让奇数和偶数的情况相同
//方便下面的最长回文串的计算
for(int i=0;i<s.size();i++){
t+=s[i];
t+='#';
}
vector<int> p(t.size(),0);
int mx=0,id=0,resl=0,resc=0;
//mx为回文串最右端
//id为能达到最右端的回文串的中间
//resl为最大的回文串的半径
//resc为最长的回文串的中间位置
for(int i=1;i<t.size();i++){
//马拉车的核心算法 //判断以t[i]为中心的回文串长度
p[i]=mx>i?min(p[2*id-i],mx-i):1;
//额外匹配的部分
while(t[i-p[i]]==t[i+p[i]]) ++p[i];
if(mx<i+p[i]){
mx=p[i]+i;
id=i;
}
//保留最长的部分
if(resl<p[i]){
resl=p[i];
resc=i;
}
}
/*最长的回文串的范围为 (最长的回文串的中间位置-最长的回文串的半径)/2的位置 到 (最长的回文串的半径-1)的位置 */
cout << s.substr((resc-resl)/2,resl-1);
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/140935.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...