算法练习day18——190409（Manacher）
1.Manacher算法
一個(gè)串中，找到最長(zhǎng)的回文子串。
1.1 暴力解決
得解決長(zhǎng)度為奇數(shù)的回文和長(zhǎng)度為偶數(shù)的回文。
1.1.1 奇回文
- i位置自己肯定構(gòu)成回文；長(zhǎng)度為1
- i+1位置和i-1位置相不相等？相等，構(gòu)成回文。長(zhǎng)度為3
- i+2位置和i-2位置相不相等？相等，構(gòu)成回文。長(zhǎng)度為5
1.1.2 偶回文
1.1.1 中的方法不適用
1.1.3 解決方法
向字符串的開(kāi)頭、中間和結(jié)尾加?xùn)|西。
既有奇回文：11311
又有偶回文：11
處理：
然后計(jì)算每一位的回文長(zhǎng)度：
最終結(jié)果是：11/2=5
此方法適用于奇回文和偶回文。
添加的字符無(wú)論啥都可以。因?yàn)樘砑拥淖址粫?huì)和原字符串中的字符進(jìn)行比較，只是和添加的字符比較（實(shí)軸永遠(yuǎn)和實(shí)軸比較，虛軸和虛軸比較）。
時(shí)間復(fù)雜度：
2.概念
2.1 回文直徑
回文半徑
在Manacher算法中，需要準(zhǔn)備一個(gè)數(shù)組——回文半徑數(shù)組。存以每個(gè)位置為中心的情況下，可括出來(lái)的回文半徑的長(zhǎng)度。
加速：數(shù)組后面的位置的值能否利用前面的值，減少計(jì)算，實(shí)現(xiàn)加速。
2.2 最右回文右邊界
所有回文半徑中最靠右的位置。
初始：R在-1的位置；
0位置：只能擴(kuò)到自己；
1位置：可以擴(kuò)到2位置（#1#）
2位置：不行
3位置：可擴(kuò)到6位置(#1#2#1#)
表示的是：每個(gè)位置下，R最右能到的位置。
3右邊擴(kuò)到了最右的0位置。
2.3 回文右邊界的中心
C表示：第一次取得這個(gè)最右邊界的中心位置。
0位置時(shí)，它的C是3.
3的右邊界到它右邊的1，后面的2的右邊界也是2后面的1，但是1的C=3的位置（記錄的是第一次到達(dá)的）。
3.分情況討論
3.1 i位置不在回文右邊界中——
比如剛開(kāi)始的時(shí)候，R在-1位置，i在1位置。就是i不在回文右邊界。
則暴力擴(kuò)。
時(shí)間復(fù)雜度：R的變化范圍是從0~N，所有擴(kuò)的范圍都在推后R，而且不會(huì)回退，所以總的時(shí)間復(fù)雜度是
3.2 i位置在回文右邊界的里面
位置1的回文右邊界在2位置，當(dāng)i為2時(shí)，它在回文右邊界的里面。
3.2.1 i'的回文半徑在L里面——
由C和R得到回文左邊界L，假設(shè)此時(shí)i的位置如圖所示：
C肯定在i的左邊。關(guān)于C做i的對(duì)稱點(diǎn)i'：
由回文數(shù)組中i'的回文半徑，可得到一下多個(gè)可能性：
可能性1：i'的回文區(qū)域在L和C的中間
舉例：
C：在F的位置
F的R和L在K位置
i'和i在b的位置
i'為重新的回文是aba，完全在L和C中間。
結(jié)論：i位置的回文半徑和i'的相等
證明：
3.2.2 L和R沒(méi)包住小L和小R——
舉例：
此時(shí)i的回文半徑就是i到R。
證明：
過(guò)程：
3.2.3 L壓線
舉例：
這種i的回文半徑能不能擴(kuò)的更大需要嘗試。上例中，由于k=k，所以可以擴(kuò)。
如下圖，k≠s，不可以擴(kuò)
時(shí)間復(fù)雜度同3.1：
4.應(yīng)用
給定一個(gè)字符串，要求只能在串后面添加字符，使之成為一個(gè)回文串。要求添加的字符數(shù)最少。
比如，給定：
添加cba會(huì)使上串變?yōu)榛匚拇?#xff0c;且最短。
它就是在求必須包含最后一個(gè)字符（"1"）的情況下，最長(zhǎng)回文串是多少。前面不是的部分（“abc”）逆序過(guò)來(lái)，就是答案。
改寫Manacher：
- 一直求每個(gè)位置的回文半徑。
- 當(dāng)R到達(dá)最后一個(gè)位置的時(shí)候，停。得到回文半徑到R的位置C。此時(shí)有R和C。
- 然后將R以C為中心，對(duì)稱到R’。即得包含最后一個(gè)位置的最長(zhǎng)回文串。
- 然后將前面剩余部分逆序，添加到給定字符串的后面。
?
比如：
?
總結(jié)
以上是生活随笔為你收集整理的算法练习day18——190409（Manacher）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 算法练习day17——190405
- 下一篇： 算法练习day19——190410（数组