马拉车算法(求最长回文串)

参考博客：

• https://blog.csdn.net/_/article/details/
• https://blog.csdn.net/u0/article/details/
• https://blog.csdn.net/_/article/details/?utm_source=app
• https://www.cnblogs.com/grandyang/p/4475985.html

马拉车算法:

• 什么是马拉车?
  Manacher算法，又叫“马拉车”，它可以在时间复杂度和空间复杂度都是O(n)的情况下，求出一个字符串的最长回文串长度(一般用法,也可以求字符串中回文串的个数)
  
  
• 第一步，重组字符串
  例如: noon
  重组后:$#n#o#o#n#
  那为什么要这样做呢?
  1.首先,这样做的好处是不论原字符串是奇数还是偶数个，处理之后得到的字符串的个数都是奇数个，这样就不用分情况讨论了，而可以一起搞定。
  2.接下来我们还需要和处理后的字符串t等长的数组p，其中 p[i] 表示以 t[i] 字符为中心的回文子串的半径，若 p[i] = 1，则该回文子串就是 t[i] 本身，那么我们来看一个简单的例子：

  
  
  
  
  
  
  
  
  
  

  # 1 # 2 # 2 # 1 # 2 # 2 # 1 2 1 2 5 2 1 6 1 2 3 2 1 

• 第二步，理解下面这段代码

  // id 代表中心位置， mx 代表最右边的位置 p[i] = mx > i ? min(p[id * 2 - i],mx - i):1; 

• 马拉车完整代码(求最长回文子串的长度):

/* 马拉车模板题: https://www.luogu.org/problemnew/solution/P3805 */ //求最长回文串的长度 #include  
     using namespace std; const int MAXN = ; int hw[MAXN]; //马拉车 inline int Manacher(string s) { 
    //转换字符串 memset(hw, 0, sizeof(hw)); int len = s.length(); string nowString = "$#"; for(int i = 0; i < len; i++){ 
    nowString += s[i]; nowString += "#"; } //防止越界访问 len = nowString.length(); int maxRight = 0, mid = 0, maxAns = 0; //maxRight 最右边的位置 mid 中心的位置 maxAns 最长回文串的半径 for(int i = 1; i < len; i++){ 
    if(maxRight > i){ 
    //当中心点没超过最右边maxRight hw[i] = min(maxRight - i, hw[(mid<<1) - i]); } else{ 
    //否则,就重新往外扩 hw[i] = 1; } //如果当前不是最长, 就往外扩 while(nowString[i + hw[i]] == nowString[i - hw[i]]){ 
    ++hw[i]; } //更新最右边的位置, 同时更新最长字串的半径 if(i + hw[i] > maxRight){ 
    maxRight = i + hw[i]; mid = i; } maxAns = max(hw[i], maxAns); } //最长字串的长度等于半径减1 return (maxAns - 1); } int main() { 
    ios::sync_with_stdio(false); string s; while(cin >> s){ 
    cout << Manacher(s) << endl; } return 0; } 

• 马拉车求最长回文串的个数

//求回文串的个数 inline int Manacher(string s) { 
    //转换字符串 memset(hw, 0, sizeof(hw)); int len = s.length(); string nowString = "$#"; for(int i = 0; i < len; i++){ 
    nowString += s[i]; nowString += "#"; } //防止越界访问 nowString += "^"; len = nowString.length(); int maxRight = 0, mid = 0, maxAns = 0, numAns = 0; //maxRight 最右边的位置 mid 中心的位置 maxAns 最长回文串的半径 for(int i = 1; i < len; i++){ 
    if(maxRight > i){ 
    //当中心点没超过最右边maxRight hw[i] = min(maxRight - i, hw[(mid<<1) - i]); } else{ 
    //否则,就重新往外扩 hw[i] = 1; } //如果当前不是最长, 就往外扩 while(nowString[i + hw[i]] == nowString[i - hw[i]]){ 
    ++hw[i]; } //更新最右边的位置, 同时更新最长字串的半径 if(i + hw[i] > maxRight){ 
    maxRight = i + hw[i]; mid = i; } //求最长回文串的长度 //maxAns = max(hw[i], maxAns); //求回文串的个数 numAns += (hw[i] / 2); } //最长字串的长度等于半径减1 //return (maxAns - 1); //回文串的个数 return numAns; } 

这里我们来探讨下为什么是:

//求回文串的个数 numAns += (hw[i] / 2); 

• 求最长回文串

//求最长回文串 inline string Manacher(string s) { 
    //转换字符串 memset(hw, 0, sizeof(hw)); int len = s.length(); string nowString = "$#"; for(int i = 0; i < len; i++){ 
    nowString += s[i]; nowString += "#"; } //防止越界访问 nowString += "^"; len = nowString.length(); int maxRight = 0, mid = 0, maxLen = 0, maxPoint = 0; //maxRight 最右边的位置 mid 中心的位置 maxAns 最长回文串的半径 for(int i = 1; i < len; i++){ 
    if(maxRight > i){ 
    //当中心点没超过最右边maxRight hw[i] = min(maxRight - i, hw[(mid<<1) - i]); } else{ 
    //否则,就重新往外扩 hw[i] = 1; } //如果当前不是最长, 就往外扩 while(nowString[i + hw[i]] == nowString[i - hw[i]]){ 
    ++hw[i]; } //更新最右边的位置, 同时更新最长字串的半径 if(i + hw[i] > maxRight){ 
    maxRight = i + hw[i]; mid = i; } if(hw[i] > maxLen){ 
    maxLen = hw[i]; maxPoint = i; //最长回文串的中心位置 } } //截取最长回文串 //这里为啥这样写,在本博客前文已经提到过: 1. 第一步,重组字符串 return s.substr((maxPoint - maxLen) / 2, maxLen - 1); } 

后续再补上一些例题,以及求字符串中所有的回文串个数,最长的回文串!

2019.07.26, 已经将基本的马拉车算法应用补上.

待补题: 杭电6599

http://acm.hdu.edu.cn/showproblem.php?pid=6599