秋招总结，总结笔试面试撕过的代码。

玄学面试 经过这么多场面试发现运气真的很重要。半是为了回馈牛客，半是总结一下笔试面试撕过的代码和刷过的算法题吧。

先从华为面试手撕过的最长回文子串开始，一开始没听清楚题目，以为是最长回文子序列用动态规划做，后面再提。

有关回文串的解法可以在线性的时间内解决，利用Manacher算法，简而言之就是用一个数组next来保存以当前位置为中心的回文半径，典型的利用空间换取时间。当然为了统一奇回文和偶回文，可以先对原字符串进行操作，比如把aa变成#a#a#。这样就都能变成一个奇回文的问题。算法的核心点是如何保证在线性时间内更新这个回文半径数组。有左神的书可以去看看书，这里简要地进行一个总结。为什么不画图，大家自己对着文字画画图再进行理解的话印象就很深不然像看小说一样看过就忘（其实就是懒）。

maxRight表示一个最右指针由next[index]+index得到，如果当前位置pos小于index，那么pos以index为对称中心对称过去的pos'=2*index-pos，这时候如果pos'-next[pos']>index-next[index]说明next[pos]=next[pos'],如果是小于的情况呢，next[pos]=maxRight-pos再将其扩展出去即可

核心代码如下

next[pos]=pos<maxRight?min(next[2*index-pos],maxRight-pos):1; while(pos+next[pos]<s.length()&&pos-next[pos]>=0&&s[pos+next[pos]]==s[pos-next[pos]])next[pos]++; if(pos+next[pos]>maxRight){ maxRight=pos+dp[pos]; index=pos; }

还有最短回文串这题目很好成功地串联了Manacher算法和KMP算法。如果用Manacher算法做那么就是求pos-next[pos]==0，pos最大的位置。接下来说说KMP算法（继续不想画图），左神的书上也有具体描述。这里先参考力扣上类似有限状态机的解法，有限状态机也可以求解有效数字，又扯远了。

比如match串是ababac，我们可以假设0a1b2a3b4a5c6。一开始是状态0，当遇到a时从状态0变成了状态1（因为ababa的首字母是a）遇到其他字符状态0变成了状态0。如果是状态1的话继续匹配如果遇到b时那么是不是就能从状态1转到2...也就是每一个状态遇到不同的字母时都会转化到不同的状态。接下来就是KMP的核心思想最大前缀后缀的问题，假设我们处于状态5，遇到c当然是转为状态6，遇到b呢？

遇到b会转为状态4，为什么？ababab的最大前缀（包含首字母不包含尾字母）是不是abab与最大后缀（包含尾字母且不包含首字母）abab是不是一样。所以会转到状态4，因为状态4是匹配完毕的abab。代码的难点在于找到当前匹配的最大前缀后缀问题并如何一层层的更新状态。

我们先一步步来最初的状态是0。那么第0次更新后1 0 0（遇到a转1，其余转0）这时候a的最大前缀后缀fix是0，第1次更新1 2 0（遇到a转1，遇到b转2，遇到c转0）这时ab的最大前缀fix还是0，第三次更新3 0 0这时aba的最大前缀后缀fix是1...

坚信一点就可以了就是你当前干的时候大部分前面都干过了Don't Repeat Yourself，你需要做的就是当前的一点点工作大部分前面都干过了是：从哪个状态转移到哪个状态最大前缀后缀大部分都帮你干过了你只需要跟着它走 for(int c='a';c<='z';c++) transfer[state][c]=transfer[fix][c],你需要做的工作：首先是更新到下一步状态transfer[state][s[state]]=state+1,再更新最大前缀fix=transfer[fix][s[state]]分析下复杂度是26*match.length()，在与source匹配的复杂度是source.length()，所以复杂度是O(N)+O(M)。

压缩成一维数组的话这个过程肯定没这么干脆了，它会先寻找最近一次匹配的最大前缀后缀再逐步回退更新。左神的一顿分析是小于O(2M)。

理解了这两个算法此类题目随便做了。

明天随缘更新下最长回文子序列从而引申的动态规划问题