LeetCode 214. Shortest Palindrome(回文串，回文树，KMP)
- 2020 年 2 月 18 日
- 筆記
https://leetcode.com/problems/shortest-palindrome/
好题目啊！
题目：
Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
Example 1:
Input: "aacecaaa" Output: "aaacecaaa" Example 2:
Input: "abcd" Output: "dcbabcd"
题意：给你一个字符串，让你在这个字符串前面加入最少的字符，让整个字符串变成一个回文串。
题解：回文串，让人第一联想到的是什么呢？我联想的第一个是动态规划。但是字符串长度超过5万，怕是要超时。接着我联想到了回文树。这是个解决回文串问题的神器。最后看题解，也可以用KMP解决。
首先，根据题目的意思，我们找一个从左边第一个字符开始的最长回文串。首先用回文树怎么解决呢？简直是杀鸡用屠龙刀！
输入一个字符串，建回文树。我们能计算那些问题呢？我轻轻列举一下，字符串中有多少个不同的回文串，字符串中回文串的总数，字符串中不同回文串的数量，字符串从某个字符开始的最长回文串长度，字符串从某个字符结束的最长回文串长度，字符串从某个字符开始的回文串个数，字符串从某个字符串结束的回文串个数，字符串中奇数回文串的数量，字符串中偶数回文串的数量…………
所以这道题目，用字符串从某个字符开始的最长回文串长度，可以解决。
接下来简单介绍一个回文树：回文树是由两颗树组成，一棵树存储偶数串，一棵树存储奇数串，每个节点都是一种回文串。节点之间的边有两种，next[p][c] 表示节点p上的回文串两端加上c字符后形成的新回文串所在节点；fail[p] 表示节点p上的回文串的最长后缀回文串所在的节点。
以上是整个树的架构。 此外节点上还有别的值：该回文串的数量，该回文串后缀回文串的数量。
回文树：
#define MAX 50005 struct Tree { char s[MAX]; int cnt[MAX]; int num[MAX]; int next[MAX][26]; int fail[MAX]; int len[MAX]; int p; int last; int n; int newNode(int x) { memset(next[p],0,sizeof(next[p])); len[p]=x; cnt[p]=0; num[p]=0; return p++; } void init() { p=0; n=0; last=0; newNode(0); newNode(-1); fail[0]=1; fail[1]=0; s[0]=-1; } int GetFail(int x) { while(s[n-len[x]-1]!=s[n]) x=fail[x]; return x; } void Add(int x) { x -= 'a'; s[++n] = x; int cur = GetFail(last); if(!(last=next[cur][x])) { int now = newNode(len[cur]+2); fail[now]=next[GetFail(fail[cur])][x]; next[cur][x]= now; num[now] = num[fail[now]]+1; last = now; } cnt[last]++; } void Count() { for(int i=p-1;i>=0;i--) { cnt[fail[i]]+=cnt[i]; } } }; class Solution { public: string shortestPalindrome(string s) { Tree tree; tree.init(); for(int i=s.length()-1;i>=0;i--) { tree.Add(s[i]); } tree.Count(); int len = tree.len[tree.last]; string ans=""; for(int i=s.length()-1;i>=len;i--) { ans+=s[i]; } ans+=s; return ans; } };
KMP
这道题目还可以用KMP做，是不是感觉很厉害？ 这个思路最最最关键的地方，就是逆转思维！不知道逆转裁判你们有没有玩过。
把字符串S 逆转成S1 ，然后把Str = S + "." +S1 拼接起来，这样我们要求的S左起最长回文串，就等于Str的最长公共前后缀！是不是要逆转思维，才能想到？
最长公共前后缀是个啥？就是KMP，就是Next数组
class Solution { public: int next[MAX*2]; string shortestPalindrome(string s) { string s2=""; for(int i=s.length()-1;i>=0;i--) { s2+=s[i]; } string str=s+"."+s2; GetNext(str); int len = next[str.length()-1]; string ans=""; for(int i=s.length()-1;i>=len;i--) { ans+=s[i]; } ans+=s; return ans; } void GetNext(string s) { next[0]=0; for(int i=1;i<s.length();i++) { int p = next[i-1]; while(p>0&&s[i]!=s[p]) { p=next[p-1]; } if(s[i]==s[p]) { next[i]=p+1; } else next[i]=0; } } };
