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;          }      }    };