最容易想到的方法为遍历字符串所有可能的子串(蛮力法),判断其是否为回文字符串,然后找出最长的回文子串。但是当字符串很长的时候,这种方法的效率是非常低下的,因此,这种方法不可取。下面介绍几种相对高效的方法。
方法一:动态规划法 在采用蛮力法找回文子串的时候其实有很多字符的比较是重复的,因此,可以把前面比较的中间结果记录下来供后面使用。这就是动态规划的基本思想,那么如何根据前面查找的结果,判断后续的子串是否为回文字符串呢?下面给出判断的公式,即动态规划的状态转移公式:
给定字符串“S
0S
1S
2…S
n”,假设P(i, j)=1表示“S
iS
i+1…S
j”是回文字符串;P(i, j)=0则表示“S
iS
i+1…S
j”不是回文字符串。那么:
P(i, i)=1
如果Si==Si+1:则P(i,i+1)=1,否则P(i,i+1)=0。
如果Si+1==Sj+1:则P(i+1,j+1)=P(i,j)。
根据这几个公式,实现代码如下:
package main
import(
"fmt"
)
typeTeststruct{
startIndex int
len int
}
func(p*Test)getLlongestPalindrome(str string){
ll:=len(str)
if ll<1{
return
}
p.startIndex=0
p.len=1
//申请额外的存储空间记录查找的历史信息
historyRecord:=make([][]int, ll)
fori, _:=range historyRecord{
historyRecord[i]=make([]int, ll)
}
//初始化长度为1的回文字符串信息
fori:=0; i<ll; i++{
historyRecord[i][i]=1
}
//初始化长度为2的回文字符串信息
fori:=0; i<ll-1; i++{
if str[i]==str[i+1]{
historyRecord[i][i+1]=1
p.startlndex=i
p.len=2
}
}
//查找从长度为3开始的回文字符串
forpCen:=3; pLen<=ll; pLen++ {
fori:=0; i<ll-pLen+1; i++ {
vartmp=i+pLen- 1
if str[i]==str[tmp]&&historyRecord[i+ 1 ] [trap- 1 ]== 1 {
historyRecord[i][tmp]=1
p.startIndex=i
p.len=pLen
}
}
}
}
//对字符串str,以c1和c2为中心向两侧扩展寻找回文字串
func (p *Test) expandBothSide(str string, c1, c2 int){
n:=len(str)
for c1>=0&&c2<n&&str[c1]==str[c2] {
c1--
c2++
}
tmpStartlndex:=c1+1
tmpLen:=c2-c1-1
if tmpLen>p.len {
p.len=tmpLen
p.startlndex=tmpStartIndex
}
}
func main() {
str:="abcdefgfedxyz"
t:=&Test{}
fmt.Println("方法一")
t.getLIongestPalindrome(str)
if t.startIndex!=- 1&&t.len! =- 1 {
fmt.Println("最长的回文子串为:", string(str[t.startIndex:t.startIndex+t.len]))
}else{
fmt.Println("查找失败")
}
}
程序的运行结果为
最长的回文子串为:defgfed
算法性能分析: 这种方法的时间复杂度为O(n
2),空间复杂度也为O(n
2)。
此外,还有另外一种动态规划的方法来实现最长回文字符串的查找。主要思路为:对于给定的字符串str1,求出对其进行逆序的字符串str2,然后str1与str2的最长公共子串就是str1的最长回文子串。
方法二:中心扩展法 判断一个字符串是否为回文字符串最简单的方法为:从字符串最中间的字符开始向两边扩展,通过比较左右两边字符是否相等就可以确定这个字符串是否为回文字符串。这种方法对于字符串长度为奇数和偶数的情况需要分别对待。例如:对于字符串“aba”,就可以从最中间的位置b开始向两边扩展;但是对于字符串“baab”,就需要从中间的两个字母开始分别向左右两边扩展。
基于回文字符串的这个特点,可以设计这样一个方法来找回文字符串:对于字符串中的每个字符C
i,向两边扩展,找出以这个字符为中心的回文子串的长度。由于上面介绍的回文字符串长度的奇偶性,这里需要分两种情况:①以ci为中心向两边扩展;②以ci和C
i+1为中心向两边扩展。实现代码如下:
package main
import(
"fmt"
)
typeTeststruct{
startIndex int
len int
}
//对字符串str,以c1和c2为中心向两侧扩展寻找回文子串
func(p*Test)expandBothSide(str string, c1, c2 int){
n:=len(str)
for c1>=0&&c2<n&&str[c1]==str[c2]{
c1--
c2++
}
tmpStartIndex:=c1+1
tmpLen:=c2-c1-1
if tmpLen>p.len{
p.len=tmpLen
p.startIndex=tmpStartIndex
}
}
//找出字符串最长的回文子串
func(p*Test)getLlongestPalindrome2(str string){
n:=len(str)
if n<1{
return
}
fori,_:=range str{
//找回文字符串长度为奇数的情况(从第i个字符向两边扩展)
p.expandBothSide(str, i, j);
//找回文字符串长度为偶数的情况(从第i和i+1两个字符字符向两边扩展)
p.expandBothSide(str, i, i+1)
}
}
func main(){
str:="abcdefgfedxyz"
fmt.Println("方法二")
t:=&Test{}
t.getLlongestPalindrome2(str)
if t.startIndex!=-1&&t.len!=-1{
fmt.Println("最长的回文子串为:", string(str[t.startIndex:t.startIndex+t.len]))
}else{
fmt.Println("查找失败")
}
}
算法性能分析: 这种方法的时间复杂度为O(n
2),空间复杂度为O(1)。
方法三:Manacher算法 方法二需要根据字符串的长度分偶数与奇数两种不同情况单独处理,Manacher算法可以通过向相邻字符中插入一个分隔符,把回文字符串的长度都变为奇数,从而可以对这两种情况统一处理。例如:对字符串“aba”插入分隔符后变为“*a*b*a*”,回文字符串的长度还是奇数。对字符串“aa”插入分隔符后变为“*a*a*",回文字符串长度也是奇数。因此,采用这种方法后可以对这两种情况统一进行处理。
Manacher算法的主要思路为:首先在字符串中相邻的字符中插入分割字符,字符串的首尾也插入分割字符(字符串中不存在的字符,本例以字符*为例作为分割字符)。接着用另外的一个辅助数组P来记录以每个字符为中心对应的回文字符串的信息。P[i]记录了以字符串第i个字符为中心的回文字符串的半径(包含这个字符),以P[i]为中心的回文字符串的长度为2*P[i]-1。P[i]-1就是这个回文字符串在原来字符串中的长度。例如:“*a*b*a*”对应的辅助数组P为:{1,2,1,4,1,2,1},最大值为P[3]=4,那么原回文字符串的长度则为4-1=3。
那么如何来计算P[i]的值呢,如下图所示可以分为四种情况来讨论:
假设在计算P[i]的时候,在已经求出的P[id](id<i)中,找出使得id+p[id]的值为最大的id,即找出这些回文字符串的尾字符下标最大的回文字符的中心的下标id。
(1)i没有落到P[id]对应的回文字符串中(如上图(1))。此时因为没有参考的值,因此,只能把字符串第i个字符作为中心,向两边扩展来求P[i]的值。
(2)i落到了P[id]对应的回文字符串中,此时可以把id当作对称点,找出i对称的位置2*id-i,如果P[2*id-i]对应的回文字符的左半部分有一部分落在P[id]内,另外一部分落在P[id]外(如上图(2)),那么P[i]=id+P[id]-i,也就是P[i]的值等于P[id]与P[2*id-i]重叠部分的长度。需要注意的是,P[i]不可能比id+P[id]-i更大,证明过程如下:假设P[i]>id+P[id]-i,以i为中心的回文字符串可以延长a、b两部分(延长的长度足够小,使得P[i]<P[2*id-i]),如上图(2)所示:根据回文字符串的特性可以得出:a=b,找出a与b以id为对称点的子串d、c。由于d和c落在了P[2*id-i]内,因此,c=d,又因为b和c落在了P[id]内,因此,b=c,所以,可以得到a=d,这与已经求出的P[id]矛盾,因此,p[id]的值不可能更大。
(3)i落到了P[id]对应的回文字符串中,把id当作对称点,找出i对称的位置2*id-i,如果P[2*id-i]对应的回文字符的左半部分与P[id]对应的回文字符的左半部分完全重叠,则P[i]的最小值为P[2*id-i],在此基础上继续想两边扩展,求出P[i]的值。
(4)i落到了P[id]对应的回文字符串中,把id当作对称点,找出i对称的位置2*id-i,如果P[2*id-i]对应的回文字符的左半部分完全落在了P[id]对应的回文字符的左半部分,则P[i]=P[2*id-i]。
根据以上这四种情况可以得出结论:P[i]>=MIN(P[2*id-i],P[id]-i)。在计算的时候可以先求出P[i]=MIN(P[2*id-i],P[id]-i),然后在此基础上向两边继续扩展寻找最长的回文子串,根据这个思路的实现代码如下:
package main
import (
"fmt"
."github.com/isdamir/gotype"//引入定义的数据结构
)
typeManacherstruct {
center int
palindromeLen int
}
//方法功能:找出字符串最长的回文子串
//输入参数:str为字符串,center为回文字符的中心字符,len表示回文字符串长度
//如果长度为偶数,center表示中间偏左边的那个字符的位置
func (p *Manacher) Manacher(str string){
ll:=len(str)
newLen:=2*ll+1
//插入分隔符后的字符串
s:=make([]rune, newLen)
pp:=make([]int, newLen)
//id表示以第id个字符为中心的回文字符串最右端的下标值最大
id:=0
fori:=0; i<newLen; i++ {
s[i]='*'
pp[i]=0
}
fori:=0; i<ll; i++ {
s[(i+ 1)*2]=rune(str[i])
}
p.center=-1
p.palindromeLen=-1
//求解p数组
fori:=1; i<newLen; i++{
if id+pp[id]>i{//图中(1), (2), (3)三种情况
pp[i]=Min(id+pp[id]-i, pp[2*id-i])
}else{
//对应图中第(1)种情况
pp[i]=1
}
//然后接着向左右两边扩展求最长的回文子串
for i+pp[i]<newLen&&i-pp[i]>0&&s[i-pp[i]]==s[i+pp[i]] {
pp[i]++
}
//求出当前更大的回文字符串最后端的下标
if i+pp[i]>id+pp[id] {
id=i
}
//求出当前更长的回文字符串
if pp[i]-1>p.palindromeLen{
p.center=(i+1)/2-1
p.palindromeLen=pp[i]-1//更新最长回文子串的长度
}
}
}
func main(){
str:="abcbax"
m:=&Manacher{}
m.Manacher(str)
if m.center!=-1&&m.palindromeLen!=-1 {
fmt.Print("最长的回文子串为:")
//回文字符串长度为奇数
if m.palindromeLen%2==1{
fori:=m.center-m.palindromeLen/2; i<=m.center+m.palindromeLen/2; i++{
fmt.Print(string(str[i]))
}
}else{//回文字符串长度为偶数
fori:=m.center-m.palindromeLen/2; i<m.center+m.palindromeLen/2; i++{
fmt.Print(string(str[i]))
}
}
}else{
fmt.Println("查找失败")
}
fmt.Println()
}
程序的运行结果为
最长的回文子串为:abcba
算法性能分析: 这种方法的时间复杂度和空间复杂度都为O(n)。