首页 > 代码库 > 最长回文字串理解（学习Manacher's algorithm）
最长回文字串理解（学习Manacher's algorithm）
关于字符串的子串问题，我们经常需要利用的是已经访问的部分的信息，来降低复杂度，和提高效率；在求最长回文子串的问题中，Manacher‘s algorithm提供了一种很好的机制，虽然部分地方不太容易理解
先说下核心的思想：先对原字符串进行预处理，将字符串"abc"转换为"$#a#b#c#"的形式，既避免了访问越界的问题，又保证每一个字符有至少一个对称的串（真字符，或是假的“#”）
预留两对变量（当前得到的中心位置“center”，和字符串右侧最远位置“R”，以及对称的左侧“L”）（当前访问字符位置“i”，以及相对当前访问位置“center”的对称位置“i_"）
#include <string.h>#include <stdio.h>#include <iostream>using namespace std;void preprocess(char str[],char result[]);int min(int a, int b);int p[2020];int main(){ int center,i,i_,L,R,j; char str[1010],result[2020]; int maxlen, index,len; cin.getline(str,1000,‘\n‘); preprocess(str,result); /*printf("%s",result);*/ //handle the string center=0,R=0; p[0]=0; len = strlen(result); //i from 1,so the begging position is placed ‘$‘ to avoid the segment error for(i=1;i<len-1;i++){ i_=center*2-i;//the symmetric position L=center*2-R; p[i] = (R > i) ? min(R - i, p[i_]) : 0; while (i + p[i] + 1<len&&result[i + p[i] + 1] == result[ i- p[i] - 1]) p[i]++; //if R expands,then modify it if (R - i <p[i]){ center = i; R = i + p[i]; } } //find the maximum length in p maxlen = 0, index = 0; for (i = 0; i < strlen(result); i++){ if (maxlen < p[i]){ maxlen = p[i]; index = i; } } printf("%d", maxlen); return 0;}void preprocess(char str[],char result[]){ int len=strlen(str),i,j; result[0]=‘$‘;//indicates the start for(i=0,j=1;i<len;i++){ result[j++]=‘#‘; result[j++]=str[i]; } result[j]=‘#‘; result[j+1]=‘\0‘;}int min(int a, int b){ if (a < b) return a; else return b;}
p[i]记录的是位置i处的字符的右侧对称长度（包括str[i]自身），最关键的是理解这几句：
p[i] = (R > i) ? min(R - i, p[i_]) : 0; while (i + p[i] + 1<len&&result[i + p[i] + 1] == result[ i- p[i] - 1]) p[i]++; //if R expands,then modify it if (R - i <p[i]){ center = i; R = i + p[i]; }最长回文字串理解（学习Manacher's algorithm）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。