Update Readme.md

wisdompeak · web-flow · commit e981a658cabd · 2021-08-31T00:43:51.000-07:00
diff --git a/String/005.Longest-Palindromic-Substring/Readme.md b/String/005.Longest-Palindromic-Substring/Readme.md
@@ -3,7 +3,7 @@
 ### &#35299;&#27861;1&#65306;
 &#32771;&#34385;&#20197;&#27599;&#20010;&#23383;&#31526;&#20026;&#23545;&#31216;&#20013;&#24515;&#65288;&#25110;&#32773;&#20026;&#23545;&#31216;&#20013;&#24515;&#32447;&#24038;&#36793;&#30340;&#23383;&#31526;&#65289;&#65292;&#21516;&#26102;&#24448;&#24038;&#24448;&#21491;&#25512;&#24191;&#65292;&#30475;&#30475;&#23558;&#22238;&#25991;&#21322;&#24452;&#26368;&#38271;&#33021;&#25512;&#33267;&#21738;&#37324;&#12290;&#36825;&#20010;&#35299;&#27861;&#27604;&#36739;&#22909;&#20889;&#65292;&#22797;&#26434;&#24230;&#26159;o(N^2)
 
-### &#35299;&#27861;2&#65306;
+### &#35299;&#27861;2&#65306;KMP
 &#26377;&#20010;&#26356;&#22909;&#30340;&#32447;&#24615;&#26102;&#38388;&#30340;Manacher&#31639;&#27861;&#65292;&#21487;&#20197;&#21442;&#32771; https://segmentfault.com/a/1190000003914228 &#36825;&#37324;&#31616;&#21333;&#30340;&#20171;&#32461;&#19968;&#19979;&#31639;&#27861;&#12290;
 
 &#25105;&#20204;&#23558;s = aaaba&#65292;&#22635;&#20805;"#"&#24471;&#21040; t = #a#a#a#b#a#&#65292;&#25105;&#20204;&#20196;&#25968;&#32452;P[i]&#34920;&#31034;&#20197;t[i]&#20026;&#23545;&#31216;&#20013;&#24515;&#30340;&#26368;&#22823;&#22238;&#25991;&#21322;&#24452;&#65288;&#19981;&#21253;&#25324;t[i]&#26412;&#36523;&#65289;&#12290;&#36825;&#26679;&#20570;&#23601;&#26159;&#20026;&#20102;&#35299;&#20915;&#22238;&#25991;&#38271;&#24230;&#22855;&#20598;&#24615;&#30340;&#38382;&#39064;&#12290;&#22312;&#23383;&#31526;&#20018;t&#20013;&#65292;&#26368;&#22823;&#30340;P[i]&#23601;&#20195;&#34920;&#20102;&#26368;&#38271;&#30340;&#22238;&#25991;&#21322;&#24452;&#12290;
@@ -25,5 +25,15 @@ X  X  X  {X  X  X  X  X  X  X  X  X  X  X}  X  X  X  X  X
 &#36825;&#26679;&#65292;&#25105;&#20204;&#23601;&#21487;&#20197;&#39034;&#24207;&#22320;&#25506;&#32034;&#25152;&#26377;P[i]&#65292;&#24182;&#25214;&#21040;&#20854;&#20013;&#30340;&#26368;&#22823;&#20540;maxLen&#65292;&#21644;&#23545;&#24212;&#30340;i&#30340;&#32034;&#24341;maxCenter&#12290;&#27880;&#24847;P&#30340;&#26500;&#24314;&#26159;&#22522;&#20110;t&#30340;&#65292;&#37027;&#20040;&#22914;&#20309;&#36820;&#22238;&#22522;&#20110;s&#30340;&#37027;&#20010;&#22238;&#25991;&#20018;&#21602;&#65311;&#20854;&#23454;&#24456;&#24039;&#22937;&#65292;&#36755;&#20986;&#30340;&#23601;&#26159;:
 ```s.substr(maxCenter/2-maxLen/2,maxLen)```
 
+### &#35299;&#27861;3&#65306;Manacher
+&#26412;&#39064;&#30340;&#26412;&#36136;&#23601;&#26159;&#22312;s&#20013;&#25214;&#19968;&#20010;&#26368;&#38271;&#30340;&#12289;&#36215;&#28857;&#22312;&#24038;&#31471;&#28857;&#30340;&#22238;&#25991;&#20018;&#12290;&#28982;&#21518;&#23558;s&#38500;&#21435;&#22238;&#25991;&#20018;&#30340;&#21518;&#31471;&#22797;&#21046;&#12289;&#32763;&#36716;&#24182;&#25340;&#25509;&#22312;&#21407;s&#20018;&#30340;&#21069;&#31471;&#65292;&#23601;&#26159;&#26368;&#20248;&#30340;&#31572;&#26696;&#12290;
+
+&#25152;&#20197;&#27492;&#39064;&#30340;&#26412;&#36136;&#23601;&#26159;Manacher&#30340;&#27169;&#26495;&#39064;```005.Longest-Palindromic-Substring```&#65292;&#27714;&#20986;&#27599;&#20010;&#20301;&#32622;&#20316;&#20026;&#20013;&#24515;&#33021;&#22815;&#26500;&#36896;&#30340;&#26368;&#38271;&#22238;&#25991;&#20018;&#65292;&#26597;&#30475;&#36825;&#20010;&#22238;&#25991;&#20018;&#26159;&#21542;&#33021;&#25269;&#36798;s&#30340;&#26368;&#24038;&#31471;&#65292;&#26159;&#30340;&#35805;&#23601;&#35760;&#24405;&#19979;&#36825;&#20010;&#22238;&#25991;&#20018;&#30340;&#38271;&#24230;L&#12290;&#36755;&#20986;&#30340;&#31572;&#26696;&#26159;&#65306;
+```cpp
+string temp = s.substr(R);
+reverse(temp.begin(), temp.end());
+return temp+s;
+```
+
 
 [Leetcode Link](https://leetcode.com/problems/longest-palindromic-substring)

-Original file line number
+Diff line change
 ### 解法1：
 考虑以每个字符为对称中心（或者为对称中心线左边的字符），同时往左往右推广，看看将回文半径最长能推至哪里。这个解法比较好写，复杂度是o(N^2)
 -### 解法2：
 +### 解法2：KMP
 有个更好的线性时间的Manacher算法，可以参考 https://segmentfault.com/a/1190000003914228 这里简单的介绍一下算法。
 我们将s = aaaba，填充"#"得到 t = #a#a#a#b#a#，我们令数组P[i]表示以t[i]为对称中心的最大回文半径（不包括t[i]本身）。这样做就是为了解决回文长度奇偶性的问题。在字符串t中，最大的P[i]就代表了最长的回文半径。
 这样，我们就可以顺序地探索所有P[i]，并找到其中的最大值maxLen，和对应的i的索引maxCenter。注意P的构建是基于t的，那么如何返回基于s的那个回文串呢？其实很巧妙，输出的就是:
 ```s.substr(maxCenter/2-maxLen/2,maxLen)```
 +### 解法3：Manacher
 +本题的本质就是在s中找一个最长的、起点在左端点的回文串。然后将s除去回文串的后端复制、翻转并拼接在原s串的前端，就是最优的答案。
++
 +所以此题的本质就是Manacher的模板题```005.Longest-Palindromic-Substring```，求出每个位置作为中心能够构造的最长回文串，查看这个回文串是否能抵达s的最左端，是的话就记录下这个回文串的长度L。输出的答案是：
 +```cpp
 +string temp = s.substr(R);
 +reverse(temp.begin(), temp.end());
 +return temp+s;
 +```
++
 [Leetcode Link](https://leetcode.com/problems/longest-palindromic-substring)