#import "../template.typ": *
#pagebreak()
= Manacher

求`str`内的最长回文子串.

都需要对原字符串进行处理:
`abcd`->`#a#b#c#d#`

1. 暴力计算,遍历每个字符,然后向外扩展.复杂度 O(n^2)
2. Mancher 优化

== 暴力计算代码

== Manacher

引入
`R=-1`
`C=-1`

1. 当遍历字符串的下标没有在 R 内,暴力扩
2. 当遍历字符串的下标有在 R 内:
  `...|L...i'...C...i...R|...`
  > 为什么 i 一定在 C-R,因为 i 必然在 C,R 之后出现(C,R 一起出现)
  1. i'对应的回文子串完全在[L,R]内部:i 的回文半径等于 i'的回文半径
    `...|L..x(.i'.)y..C..y(.i.)x..R|...`
  2. i'对应的回文子串一部分在[L,R]外部:i 的回文半径 R-i+1
    `..(..x|L..i'..)..C..(..i..R|y..)..` x!=y.
  3. i'对应的回文子串左侧最远恰好在 L 处:i 的回文半径至少为 R-i+1
    `....x(|L..i'..)..C..(..i..R|)y....` x 与 y 的关系不知道

```
s-处理->str
R=-1,C=-1
pArr[]存 i 位置的回文半径
for i in range(len):
    if str[i] 在 R 内:
    暴力扩
    else:
        if(i 回文在内部):
            pArr[i]=pArr[i']
        if(i 回文在外部):
            pArr[i]=R-i+1
        if(i 回文在 L):
            pArr[i]=R-i+1
            扩
```

=== 代码实现

=== 复杂度分析

每个位置最多扩失败一次,故失败 O(n) 成功:

#tablem[
  | 分类 | i(max=n) | R(max=n) | | ---- | -------- | -------- | | 1 | + | + | |
  2.1 | + | \ | | 2.2 | + | \ | | 2.3 | + | + |
]

故成功也为 O(n)

总为 O(n)
