首页 > 代码库 > O(n) 求最长回文子串的 Manacher 算法
O(n) 求最长回文子串的 Manacher 算法
Manacher是一个可以在O(n)的时间内求出一个长度为n的字符串的算法。
以为回文子串有偶数长度，也有奇数长度，分别处理会很不方便。
所以在每两个字符中间插入一个无关字符，如‘#’，这样所有的回文子串都变为奇数长度。
两端在添加不同的无关字符防止匹配时越界。
如： abba 变成 $#a#b#b#a#&
预处理代码：
void Prepare(){ l = strlen(Str); S[0] = ‘$‘; for (int i = 0; i <= l - 1; i++) { S[(i << 1) + 1] = ‘#‘; S[(i << 1) + 2] = Str[i]; } S[(l << 1) + 1] = ‘#‘; S[(l << 1) + 2] = ‘&‘; l = (l << 1) + 2;}
求回文子串的代码：
void Manacher(){ maxLen = 0; for (int i = 1, j = 0, k; i <= l; ) { while (S[i - (j + 1)] == S[i + (j + 1)]) j++; rad[i] = j; maxLen = max(maxLen, j); for (k = 1; k <= j && rad[i - k] != rad[i] - k; k++) rad[i + k] = min(rad[i - k], rad[i] - k); i += k; j = max(0, j - k); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。