2026-06-16：最长的准回文子字符串。用go语言，给定一个只包含小写字母的字符串 s。你要在 s 的所有连续、非空子字符串中，寻找“最长的

2026-06-16：最长的准回文子字符串。用go语言，给定一个只包含小写字母的字符串 s。你要在 s 的所有连续、非空子字符串中，寻找“最长的准回文串”的长度。

其中，“准回文串”的定义是：对某个子字符串来说，只允许从中恰好删除一个字符，并且删除后剩下的字符串是回文串（即正着读和反着读都相同）。

请输出：s 中满足上述条件的最长子字符串的长度。

2 <= s.length <= 2500。

s 仅由小写英文字母组成。

输入： s = “abca”。

输出： 4。

解释：

选择子字符串 “abca”。

删除 “abca” 中的 c。

字符串变为 “aba”，它是一个回文串。

因此，”abca” 是准回文串。

题目来自力扣3844。

一、整体题目目标梳理

输入仅小写字母字符串s，长度2~2500；
准回文子串定义：连续非空子串，恰好删掉1个字符后剩余串是回文；
需求：找出所有符合条件子串里最长的长度。
样例s=abca，完整串删c得aba回文，答案4。
整套代码分为三大核心模块：

1. 稀疏表SparseTable：区间最小值O(1)查询结构；

2. 后缀数组+LCP最长公共前缀工具：快速求任意两个后缀的最长公共前缀；

3. Manacher马拉车算法遍历所有原串回文子串，结合LCP向两端拓展，计算删一个字符能得到回文的最长子串长度。

二、模块1：稀疏表 SparseTable 分步流程

作用：预处理数组，支持任意区间最小值O(1)查询，专门给LCP高度数组用。

步骤1：初始化稀疏表

1. 输入数组a、合并二元操作op（这里取min最小值）；

2. 计算数组长度n，w = log2(n)向上取整，代表稀疏表总层数；

3. 构建二维数组st：st[k][j]代表从下标j开始、长度2^k区间的运算结果；

4. 第0层st[0]直接复制原数组a，代表长度2^0=1的区间；

5. 逐层递推填充：
对每层k≥1，每个合法起点j，区间拆成前后两段各2^(k-1)：
st[k][j] = min( st[k-1][j], st[k-1][j+2^(k-1)] )。

步骤2：区间查询逻辑（左闭右开[l,r)）

1. 区间长度len=r-l，k = floor(log2(len))，取不超过区间长度的最大2次幂；

2. 用两段长度2^k的区间覆盖[l,r)：一段从l起，一段从r-2^k起；

3. 两段区间取最小值返回，单次查询无循环，O(1)。

本模块复杂度

构建：O(n log n)；单次查询O(1)；空间O(n log n)。

三、模块2：后缀数组 + LCP最长公共前缀计算流程

函数suffixArrayLCP(s)输入字符串，返回闭包函数lcp(i,j)：输入两个下标，返回s[i:]和s[j:]两个后缀的最长公共前缀长度。

步骤1：生成后缀数组sa

调用标准库suffixarray.New，得到sa数组：
sa[x]= 字典序排名第x的后缀，起始字符在原串的下标；
例：字符串abc，sa[0]是字典序最小后缀起点。

步骤2：生成rank名次数组

rank是sa的逆映射：rank[pos] = x
含义：以pos开头的后缀，字典序排名是x；恒满足rank[sa[x]] = x。

步骤3：生成height高度数组（LCP核心数组）

height[x]定义：排名第x、第x-1的两个后缀的最长公共前缀长度；height[0]=0（无前置后缀，哨兵）。
采用线性O(n)贪心算法计算height：

1. 初始化匹配长度h=0；

2. 遍历每个后缀起点i，对应排名rk=rank[i]；

3. 若上一轮匹配长度h>0，先h--（核心优化：下一个后缀公共前缀至少比上一组少1）；

4. 若当前排名rk>0（存在前一名后缀）：
取前一名后缀起点j=sa[rk-1]，从当前h开始暴力向后匹配字符s[i+h]与s[j+h]，相等则h自增；

5. 将当前h存入height[rk]。

步骤4：height数组绑定稀疏表，支持区间最小查询

对height数组构建min稀疏表，因为两个后缀rank区间内height的最小值 = 这两个后缀的LCP长度。

步骤5：lcp(i,j)闭包查询逻辑（求后缀i、j最长公共前缀）

1. 若i==j：两个后缀完全相同，公共前缀长度=字符串总长-i；

2. 取出两个后缀排名ri=rank[i], rj=rank[j]，交换保证ri

3. 查询height数组区间[ri+1, rj+1)最小值，该值就是两个后缀最长公共前缀。

本模块整体复杂度

1. 后缀数组构建：库实现O(n) / O(n log n)；

2. rank、height生成：O(n)；

3. height稀疏表预处理：O(n log n)；

4. lcp单次查询O(1)；
拼接串s + # + 反转s总长度2n+1，记m=2n+1。
空间：O(m log m)存储稀疏表、sa、rank、height数组。

四、模块3：马拉车Manacher算法 + 拓展计算准回文最长长度（核心主逻辑almostPalindromic）

输入原串s，n=len(s)，目标求最长准回文子串长度。

前置准备1：构造拼接串，用于跨正反串LCP查询

1. 生成反转串revS；

2. 拼接查询串S = s + # + revS，调用suffixArrayLCP(S)得到lcp函数；
作用：后续快速查询「原串左侧剩余字符」和「反转串右侧剩余字符」的匹配长度，实现回文向两端拓展。

前置准备2：Manacher填充串t（消除奇偶回文分类讨论）

原串s字符间插入#，首尾加哨兵^、$，格式：^#$；
转换规则：t中中心下标ti映射回原串s区间：
以ti为中心、最大回文半径halfLen[ti]的回文，对应原串子串区间[l, r] = [(i-halfLen[i])/2 , (i+halfLen[i])/2 - 2]；
[l,r]是原串s上一段天然回文子串（无需删字符，本身回文）。

步骤1：Manacher线性遍历所有回文中心，求出全部原串回文子串

1. 数组halfLen：halfLen[i]是t中以i为中心的最长回文半径；

2. 维护当前最右回文边界boxR、对应中心boxM；

3. 逐个遍历t中所有有效回文中心i：
① 若i在最右边界内，利用对称位置的回文半径快速初始化当前hl（避免重复匹配）；否则hl初始为1；
② 暴力向左右扩展匹配t[i-hl] == t[i+hl]，每匹配成功hl+1，同步更新全局最右回文边界boxM、boxR；
③ 保存当前中心最大半径halfLen[i]=hl；
④ 映射得到该回文在原串s上的原生回文区间[l, r]（本身无删除就是回文）。

步骤2：对每个原生回文区间[l,r]，分三类判断、更新全局最长答案ans

原生回文[l,r]：本身是回文，满足「删0个字符回文」；题目要求恰好删1个字符，因此需要向左右单侧拓展一段，最终整体子串仅删除1个字符就能变成回文。

分支1：当前原生回文长度 ≥ n-1

区间长度r-l+1 ≥ n-1，说明整个原串s只需要删至多1个字符就能回文，直接返回原串总长n（最优解，如样例abca），函数终止。

分支2：向左外侧删1个字符，向右无限拓展匹配

思路：保留原生回文[l,r]，删掉左侧紧邻字符s[l-1]，然后左侧剩余字符、右侧剩余字符可以成对匹配，匹配多少就能各拓展多少长度。

1. 基础增量extra初始=1（代表删除外侧单个字符的代价）；

2. 若左边还有字符l-2≥0、右边还有字符r+1
：
调用lcp查询「反转串对应后缀」与「原串右侧后缀」的公共前缀长度，匹配长度*2加到extra（左右对称拓展等量字符）；

3. 总候选长度 = 原生回文长度(r-l+1) + extra；

4. 和全局ans对比，保留最大值。

分支3：向右外侧删1个字符，向左无限拓展匹配

思路：保留原生回文[l,r]，删掉右侧紧邻字符s[r+1]，左右剩余字符成对匹配拓展。

1. extra初始=1（删除右侧单个字符）；

2. 若左边还有字符l-1≥0、右边还有字符r+2
：
调用lcp查询对应后缀公共前缀，匹配长度*2加到extra；

3. 总候选长度 = 原生回文长度 + extra；

4. 更新全局ans最大值。

步骤3：遍历完所有回文中心后，返回全局最大值ans

ans存储所有满足「恰好删1字符成回文」子串的最长长度。

五、样例 s=”abca” 完整执行流程简化演示

n=4，s = a b c a，revS = a c b a，拼接查询串S=abca。

1. 预处理S的后缀数组、rank、height、稀疏表，得到lcp函数；

2. 构造Manacher串t：^#$；

3. Manacher遍历所有中心，找到原生回文区间：

• [0,0]（a）、[1,1]（b）、[2,2]（c）、[3,3]（a）、[0,2]（aba，下标0=a、1=b、2=c不匹配，实际核心原生回文是[0,0]、[2,2]、[3,3]）；

• 遍历到完整串对应的回文中心时，原生区间[0,3]（整个abca不是原生回文，但分解出中间[c]原生回文）；

4. 处理原生区间[2,2]（字符c，长度1）：
方案：删除左侧/右侧一个字符，向两端拓展；删c左侧b不行，删c本身：保留左右a、a，匹配得到完整区间[0,3]，候选长度1+3=4；

5. 判断区间长度4 ≥ n-1=3，直接返回4，匹配样例输出。

六、总时间复杂度拆解（输入字符串长度n，2≤n≤2500）

1. 拼接查询串长度 m = 2n+1；

• 后缀数组构建：O(m log m)

• rank、height数组生成：O(m)

• height稀疏表预处理：O(m log m)

2. Manacher算法处理填充串t，长度O(n)，线性遍历：O(n)；
每个回文中心内拓展总次数O(n)，无嵌套循环；

3. Manacher单次循环内两次lcp查询，单次O(1)，总查询次数O(n)；

4. 合并化简：m=2n，log(2n)≈log n，整体主导项为 O(n log n)。
输入上限n=2500，n log n计算量极小，完全满足数据范围。

七、总额外空间复杂度拆解

1. 后缀数组sa：O(m)

2. rank数组：O(m)

3. height数组：O(m)

4. height稀疏表二维数组：O(m log m)

5. Manacher填充串t、halfLen数组：O(n)

6. 反转字符串、拼接查询串S：O(m)
主导空间消耗是稀疏表O(m log m)=O(n log n)；
其余数组均为线性O(n)级别。
总额外空间复杂度：O(n log n)

总结

1. 底层工具链：稀疏表提供区间min O(1)查询；后缀数组+height数组实现任意两后缀LCP O(1)查询；

2. 核心枚举方式：Manacher线性枚举原串全部天然回文子串，不遗漏任何回文中心；

3. 准回文判定逻辑：以天然回文为内核，单侧删除一个字符后利用LCP向两端对称拓展，计算该构造方式下子串总长度；

4. 剪枝优化：一旦找到长度≥n-1的合法子串直接返回全局最大值；

5. 复杂度结论：
总时间复杂度：O(n log n)
总额外空间复杂度：O(n log n)

Go完整代码如下：

package main

 import (
    "fmt"
    "index/suffixarray"
    "math/bits"
    "slices"
    "unsafe"
)

 type sparseTable[T any] struct {
    st [][]T
    op func(T, T) T
}

 // 时间复杂度 O(n * log n)
func newSparseTable[T any](a []T, op func(T, T) T) sparseTable[T] {
    n := len(a)
    w := bits.Len(uint(n))
    st := make([][]T, w)
    for i := range st {
        st[i] = make([]T, n)
    }
    copy(st[0], a)
    for i := 1; i < w; i++ {
        for j := range n - 1<1 {
            st[i][j] = op(st[i-1][j], st[i-1][j+1<<(i-1)])
        }
    }
    return sparseTable[T]{st, op}
}

 // [l,r) 左闭右开，下标从 0 开始
// 返回 op(nums[l:r])
// 时间复杂度 O(1)
func (s sparseTable[T]) query(l, r int) T {
    k := bits.Len(uint(r-l)) - 1
    return s.op(s.st[k][l], s.st[k][r-1< 
 
 
 
 } 
 
 
 
 
 func suffixArrayLCP(s string) 
 func(int, int) 
 int 
  { 
 
 
      
 // 后缀数组 sa（后缀序） 
 
 
      
 // sa[i] 表示后缀字典序中的第 i 个字符串（的首字母）在 s 中的位置 
 
 
      
 // 特别地，后缀 s[sa[0]:] 字典序最小，后缀 s[sa[n-1]:] 字典序最大 
 
 
      
 type 
  _tp  
 struct 
  { 
 
 
         _  [] 
 byte 
 
 
         sa [] 
 int32 
 
 
     } 
 
 
     sa := (*_tp)(unsafe.Pointer(suffixarray.New([] 
 byte 
 (s)))).sa 
 
 
 
 
      
 // 计算后缀名次数组 
 
 
      
 // 后缀 s[i:] 位于后缀字典序中的第 rank[i] 个 
 
 
      
 // 特别地，rank[0] 即 s 在后缀字典序中的排名，rank[n-1] 即 s[n-1:] 在字典序中的排名 
 
 
      
 // 相当于 sa 的反函数，即 rank[sa[i]] = i 
 
 
     rank :=  
 make 
 ([] 
 int 
 ,  
 len 
 (sa)) 
 
 
      
 for 
  i, p :=  
 range 
  sa { 
 
 
         rank[p] = i 
 
 
     } 
 
 
 
 
      
 // 计算高度数组（也叫 LCP 数组） 
 
 
      
 // height[0] = 0（哨兵） 
 
 
      
 // height[i] = LCP(s[sa[i]:], s[sa[i-1]:])  (i > 0) 
 
 
      
 // 获取 s[i] 所在位置的高度：height[rank[i]] 
 
 
     height :=  
 make 
 ([] 
 int 
 ,  
 len 
 (sa)) 
 
 
     h :=  
 0 
 
 
      
 // 计算 s 与 s[sa[rank[0]-1]:] 的 LCP（记作 LCP0） 
 
 
      
 // 计算 s[1:] 与 s[sa[rank[1]-1]:] 的 LCP（记作 LCP1） 
 
 
      
 // 计算 s[2:] 与 s[sa[rank[2]-1]:] 的 LCP 
 
 
      
 // ... 
 
 
      
 // 计算 s[n-1:] 与 s[sa[rank[n-1]-1]:] 的 LCP 
 
 
      
 // 从 LCP0 到 LCP1，我们只去掉了 s[0] 和 s[sa[rank[0]-1]] 这两个字符 
 
 
      
 // 所以 LCP1 >= LCP0 - 1 
 
 
      
 // 这样就能加快 LCP 的计算了（类似滑动窗口） 
 
 
      
 // 注：实际只计算了 n-1 对 LCP，因为我们跳过了 rank[i] = 0 的情况 
 
 
      
 for 
  i, rk :=  
 range 
  rank { 
 
 
          
 if 
  h >  
 0 
  { 
 
 
             h-- 
 
 
         } 
 
 
          
 if 
  rk >  
 0 
  { 
 
 
              
 for 
  j :=  
 int 
 (sa[rk 
 -1 
 ]); i+h <  
 len 
 (s) && j+h <  
 len 
 (s) && s[i+h] == s[j+h]; h++ { 
 
 
             } 
 
 
         } 
 
 
         height[rk] = h 
 
 
     } 
 
 
 
 
     st := newSparseTable(height,  
 func(a int, b int) 
 int 
  {  
 return 
  min(a, b) }) 
 
 
 
 
      
 // 返回 LCP(s[i:], s[j:])，即两个后缀的最长公共前缀 
 
 
     lcp :=  
 func(i, j int) 
 int 
  { 
 
 
          
 if 
  i == j { 
 
 
              
 return 
 len 
 (sa) - i 
 
 
         } 
 
 
          
 // 将 s[i:] 和 s[j:] 通过 rank 数组映射为 height 的下标 
 
 
         ri, rj := rank[i], rank[j] 
 
 
          
 if 
  ri > rj { 
 
 
             ri, rj = rj, ri 
 
 
         } 
 
 
          
 // ri+1 是因为 height 的定义是 sa[i] 和 sa[i-1] 
 
 
          
 // rj+1 是因为 query 是左闭右开 
 
 
          
 return 
  st.query(ri+ 
 1 
 , rj+ 
 1 
 ) 
 
 
     } 
 
 
      
 return 
  lcp 
 
 
 } 
 
 
 
 
 func almostPalindromic(s string) 
  (ans  
 int 
 ) { 
 
 
     n :=  
 len 
 (s) 
 
 
     revS := [] 
 byte 
 (s) 
 
 
     slices.Reverse(revS) 
 
 
     lcp := suffixArrayLCP(s +  
 "#" 
  +  
 string 
 (revS)) 
 
 
 
 
      
 // 将 s 改造为 t，这样就不需要分 len(s) 的奇偶来讨论了，因为新串 t 的每个回文子串都是奇回文串（都有回文中心） 
 
 
      
 // s 和 t 的下标转换关系： 
 
 
      
 // (si+1)*2 = ti 
 
 
      
 // ti/2-1 = si 
 
 
      
 // ti 为偶数（2,4,6,...）对应 s 中的奇回文串 
 
 
      
 // ti 为奇数（3,5,7,...）对应 s 中的偶回文串 
 
 
     t :=  
 append 
 ( 
 make 
 ([] 
 byte 
 ,  
 0 
 , n* 
 2 
 + 
 3 
 ),  
 '^' 
 ) 
 
 
      
 for 
  _, c :=  
 range 
  s { 
 
 
         t =  
 append 
 (t,  
 '#' 
 ,  
 byte 
 (c)) 
 
 
     } 
 
 
     t =  
 append 
 (t,  
 '#' 
 ,  
 '$' 
 ) 
 
 
 
 
      
 // 定义一个奇回文串的回文半径=(长度+1)/2，即保留回文中心，去掉一侧后的剩余字符串的长度 
 
 
      
 // halfLen[i] 表示在 t 上的以 t[i] 为回文中心的最长回文子串的回文半径 
 
 
      
 // 具体地，闭区间 [i-halfLen[i]+1, i+halfLen[i]-1] 是 t 上的一个回文子串 
 
 
      
 // 由于 t 中回文子串的首尾字母一定是 #，根据下标转换关系， 
 
 
      
 // 可以得到其在 s 中对应的回文子串的区间为 [(i-halfLen[i])/2, (i+halfLen[i])/2-2] 
 
 
     halfLen :=  
 make 
 ([] 
 int 
 ,  
 len 
 (t) 
 -2 
 ) 
 
 
     halfLen[ 
 1 
 ] =  
 1 
 
 
      
 // boxR 表示当前右边界下标最大的回文子串的右边界下标+1（初始化成任意 <= 0 的数都可以） 
 
 
      
 // boxM 为该最大回文子串的中心位置，二者的关系为 boxR = boxM + halfLen[boxM] 
 
 
     boxM, boxR :=  
 0 
 ,  
 0 
 
 
      
 for 
  i :=  
 2 
 ; i <  
 len 
 (halfLen); i++ {  
 // 循环的起止位置对应着原串的首尾字符 
 
 
         hl :=  
 1 
 // 注：如果题目比较的是抽象意义的值，单个值可能不满足要求，此时应初始化 hl = 0 
 
 
          
 if 
  i < boxR { 
 
 
              
 // 记 i 关于 boxM 的对称位置 i'=boxM*2-i 
 
 
              
 // 若以 i' 为中心的最长回文子串范围超出了以 boxM 为中心的回文串的范围（即 i+halfLen[i'] >= boxR） 
 
 
              
 // 则 halfLen[i] 应先初始化为已知的回文半径 boxR-i，然后再继续暴力匹配 
 
 
              
 // 否则 halfLen[i] 与 halfLen[i'] 相等 
 
 
             hl = min(halfLen[boxM* 
 2 
 -i], boxR-i) 
 
 
         } 
 
 
          
 // 暴力扩展 
 
 
          
 // 算法的复杂度取决于这部分执行的次数 
 
 
          
 // 由于扩展之后 boxR 必然会更新（右移），且扩展的的次数就是 boxR 右移的次数 
 
 
          
 // 因此算法的复杂度 = O(len(t)) = O(len(s)) 
 
 
          
 for 
  t[i-hl] == t[i+hl] { 
 
 
             hl++ 
 
 
             boxM, boxR = i, i+hl 
 
 
         } 
 
 
         halfLen[i] = hl 
 
 
 
 
          
 // 闭区间 [(i-halfLen[i])/2, (i+halfLen[i])/2-2] 是 s 上的一个回文子串 
 
 
         l, r := (i-halfLen[i])/ 
 2 
 , (i+halfLen[i])/ 
 2 
 -2 
 
 
 
 
          
 // s 本身是回文串，或者删除两端一个字母后是回文串 
 
 
          
 if 
  r-l+ 
 1 
  >= n 
 -1 
  { 
 
 
              
 return 
  n  
 // 如果 s 本身是回文串，删除回文中心后，仍然是回文串 
 
 
         } 
 
 
 
 
          
 // 删除 s[l-1]，继续扩展 
 
 
         extra :=  
 1 
 // 删除 [l,r] 外侧的一个字母 
 
 
          
 if 
  l 
 -2 
  >=  
 0 
  && r+ 
 1 
  < n { 
 
 
             extra += lcp(r+ 
 1 
 , n* 
 2 
 -l+ 
 2 
 ) *  
 2 
 
 
         } 
 
 
         ans = max(ans, r-l+ 
 1 
 +extra) 
 
 
 
 
          
 // 删除 s[r+1]，继续扩展 
 
 
         extra =  
 1 
 // 删除 [l,r] 外侧的一个字母 
 
 
          
 if 
  l 
 -1 
  >=  
 0 
  && r+ 
 2 
  < n { 
 
 
             extra += lcp(r+ 
 2 
 , n* 
 2 
 -l+ 
 1 
 ) *  
 2 
 
 
         } 
 
 
         ans = max(ans, r-l+ 
 1 
 +extra) 
 
 
     } 
 
 
 
 
      
 return 
 
 
 } 
 
 
 
 
 func main() 
  { 
 
 
     s :=  
 "abca" 
 
 
     result := almostPalindromic(s) 
 
 
     fmt.Println(result) 
 
 
 } 
 
 
 

Python完整代码如下：

# -*-coding:utf-8-*-

 import math
import bisect
from typing import List, Tuple, Callable, Any

 class SparseTable:
    """稀疏表，支持O(1)区间查询（要求操作满足结合律）"""
    def __init__(self, a: List[Any], op: Callable[[Any, Any], Any]):
        n = len(a)
        w = n.bit_length()
        self.st = [[0] * n for _ in range(w)]
        self.op = op
        self.st[0] = a.copy()
        for i in range(1, w):
            step = 1 << (i - 1)
            for j in range(n - (1 << i) + 1):
                self.st[i][j] = op(self.st[i-1][j], self.st[i-1][j + step])

     def query(self, l: int, r: int) -> Any:
        """查询区间[l, r)"""
        k = (r - l).bit_length() - 1
        return self.op(self.st[k][l], self.st[k][r - (1 << k)])

 def suffix_array_lcp(s: str) -> Callable[[int, int], int]:
    """
    构建后缀数组的LCP查询函数
    返回一个函数lcp(i, j)，表示后缀s[i:]和s[j:]的最长公共前缀长度
    """
    n = len(s)
    # 使用Python内置排序构建后缀数组（简单实现，实际可优化）
    suffixes = [(s[i:], i) for i in range(n)]
    suffixes.sort(key=lambda x: x[0])
    sa = [idx for _, idx in suffixes]

     # 计算rank数组
    rank = [0] * n
    for i, pos in enumerate(sa):
        rank[pos] = i

     # 计算height数组
    height = [0] * n
    h = 0
    for i in range(n):
        rk = rank[i]
        if rk > 0:
            j = sa[rk - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            height[rk] = h
            if h > 0:
                h -= 1

     st = SparseTable(height, min)

     def lcp(i: int, j: int) -> int:
        if i == j:
            return n - i
        ri, rj = rank[i], rank[j]
        if ri > rj:
            ri, rj = rj, ri
        return st.query(ri + 1, rj + 1)

     return lcp

 def almost_palindromic(s: str) -> int:
    """返回最长几乎回文子串的长度（最多删除一个字符）"""
    n = len(s)
    rev_s = s[::-1]
    lcp = suffix_array_lcp(s + "#" + rev_s)

     # 构建改造后的字符串t，用于处理奇偶回文统一
    t = ['^']
    for c in s:
        t.append('#')
        t.append(c)
    t.append('#')
    t.append('$')
    t_str = ''.join(t)

     half_len = [0] * (len(t_str) - 2)
    half_len[1] = 1
    box_m, box_r = 0, 0
    ans = 0

     for i in range(2, len(half_len)):
        hl = 1
        if i < box_r:
            hl = min(half_len[2 * box_m - i], box_r - i)

         # 暴力扩展
        while t_str[i - hl] == t_str[i + hl]:
            hl += 1
            box_m, box_r = i, i + hl

         half_len[i] = hl

         # 计算在原始字符串s中的区间 [l, r]
        l = (i - hl) // 2
        r = (i + hl) // 2 - 2

         # 如果当前回文子串长度已经 >= n-1，则可以直接返回n
        if r - l + 1 >= n - 1:
            return n

         # 删除左侧字符 l-1
        extra = 1
        if l - 2 >= 0 and r + 1 < n:
            # 注意lcp的调用参数需要根据原始字符串计算
            extra += lcp(r + 1, n * 2 - l + 2) * 2
        ans = max(ans, r - l + 1 + extra)

         # 删除右侧字符 r+1
        extra = 1
        if l - 1 >= 0 and r + 2 < n:
            extra += lcp(r + 2, n * 2 - l + 1) * 2
        ans = max(ans, r - l + 1 + extra)

     return ans

 if __name__ == "__main__":
    s = "abca"
    result = almost_palindromic(s)
    print(result)  

C++完整代码如下：

  

  

    

  

  

  

  


 using namespace std;

 template 
 
class SparseTable {
private:
    vector 
 
 > st; 
 
    function 
 
 op; 
 

 public:
    // 时间复杂度 O(n * log n)
    SparseTable(const vector 
 
 & a, function 
 
 op) : op(op) { 
 
 
        int n = a.size();
        int w = 32 - __builtin_clz(n); // bits.Len(uint(n))
        st.resize(w, vector 
 
 (n)); 
 

         for (int i = 0; i < n; i++) {
            st[0][i] = a[i];
        }

         for (int i = 1; i < w; i++) {
            int step = 1 << (i - 1);
            for (int j = 0; j + (1 << i) <= n; j++) {
                st[i][j] = op(st[i-1][j], st[i-1][j + step]);
            }
        }
    }

     // [l, r) 左闭右开，下标从0开始
    // 返回 op(nums[l:r])
    // 时间复杂度 O(1)
    T query(int l, int r) const {
        int k = 31 - __builtin_clz(r - l); // bits.Len(uint(r-l)) - 1
        return op(st[k][l], st[k][r - (1 << k)]);
    }
};

 // 后缀数组的LCP查询函数
function suffixArrayLCP(conststring& s) {
    int n = s.length();

     // 构建后缀数组（使用简单但有效的方法）
    vector sa(n);
    for (int i = 0; i < n; i++) sa[i] = i;

     // 使用lambda进行后缀排序
    sort(sa.begin(), sa.end(), [&](int i, int j) {
        return s.substr(i) < s.substr(j);
    });

     // 计算rank数组
    vector rank(n);
    for (int i = 0; i < n; i++) {
        rank[sa[i]] = i;
    }

     // 计算height数组
    vector height(n);
    int h = 0;
    for (int i = 0; i < n; i++) {
        int rk = rank[i];
        if (rk > 0) {
            int j = sa[rk - 1];
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
                h++;
            }
            height[rk] = h;
            if (h > 0) h--;
        }
    }

     SparseTable st(height, [](int a, int b) { return min(a, b); });

     // 返回LCP函数
    return [=](int i, int j) -> int {
        if (i == j) return n - i;
        int ri = rank[i], rj = rank[j];
        if (ri > rj) swap(ri, rj);
        return st.query(ri + 1, rj + 1);
    };
}

 int almostPalindromic(conststring& s) {
    int n = s.length();
    string revS = s;
    reverse(revS.begin(), revS.end());
    auto lcp = suffixArrayLCP(s + "#" + revS);

     // 将s改造为t，统一处理奇偶回文
    // t: ^#$
    string t = "^";
    for (char c : s) {
        t += '#';
        t += c;
    }
    t += "#$";

     vector halfLen(t.length() - 2);
    halfLen[1] = 1;
    int boxM = 0, boxR = 0;
    int ans = 0;

     for (int i = 2; i < halfLen.size(); i++) {
        int hl = 1;
        if (i < boxR) {
            hl = min(halfLen[2 * boxM - i], boxR - i);
        }

         // 暴力扩展
        while (t[i - hl] == t[i + hl]) {
            hl++;
            boxM = i;
            boxR = i + hl;
        }
        halfLen[i] = hl;

         // 闭区间 [(i-halfLen[i])/2, (i+halfLen[i])/2-2] 是s上的一个回文子串
        int l = (i - hl) / 2;
        int r = (i + hl) / 2 - 2;

         // s本身是回文串，或者删除两端一个字母后是回文串
        if (r - l + 1 >= n - 1) {
            return n;
        }

         // 删除s[l-1]，继续扩展
        int extra = 1; // 删除[l,r]外侧的一个字母
        if (l - 2 >= 0 && r + 1 < n) {
            extra += lcp(r + 1, n * 2 - l + 2) * 2;
        }
        ans = max(ans, r - l + 1 + extra);

         // 删除s[r+1]，继续扩展
        extra = 1; // 删除[l,r]外侧的一个字母
        if (l - 1 >= 0 && r + 2 < n) {
            extra += lcp(r + 2, n * 2 - l + 1) * 2;
        }
        ans = max(ans, r - l + 1 + extra);
    }

     return ans;
}

 int main() {
    string s = "abca";
    int result = almostPalindromic(s);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。