回文串
回文串
问题描述
给定一个字符串 ，判断其是否为回文串，或者找出其中的最长回文子串。
回文串是指正着读和倒着读都一样的字符串。
Manacher算法
算法思想
- 在字符串间插入特殊字符，统一奇偶长度的回文串处理
- 利用已有回文信息，避免重复计算
- 维护当前最右回文边界，加速匹配过程
时间复杂度
- 预处理时间：
- 查找时间：
- 空间复杂度：
代码实现
class Solution {
private:
string preProcess(string& s) {
string t = "#";
for (char c : s) {
t += c;
t += "#";
}
return t;
}
public:
string longestPalindrome(string s) {
string t = preProcess(s);
int n = t.length();
vector<int> p(n); // p[i]表示以i为中心的回文半径
int center = 0, right = 0;
int maxLen = 0, start = 0;
for (int i = 0; i < n; i++) {
if (i < right) {
p[i] = min(right - i, p[2 * center - i]);
}
// 中心扩展
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
t[i - p[i] - 1] == t[i + p[i] + 1]) {
p[i]++;
}
// 更新最右回文边界
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 更新最长回文子串
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substr(start, maxLen);
}
};
class Solution {
private String preProcess(String s) {
StringBuilder t = new StringBuilder("#");
for (char c : s.toCharArray()) {
t.append(c).append("#");
}
return t.toString();
}
public String longestPalindrome(String s) {
String t = preProcess(s);
int n = t.length();
int[] p = new int[n]; // p[i]表示以i为中心的回文半径
int center = 0, right = 0;
int maxLen = 0, start = 0;
for (int i = 0; i < n; i++) {
if (i < right) {
p[i] = Math.min(right - i, p[2 * center - i]);
}
// 中心扩展
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n &&
t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) {
p[i]++;
}
// 更新最右回文边界
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 更新最长回文子串
if (p[i] > maxLen) {
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substring(start, start + maxLen);
}
}
class Solution:
def preProcess(self, s: str) -> str:
return '#' + '#'.join(s) + '#'
def longestPalindrome(self, s: str) -> str:
t = self.preProcess(s)
n = len(t)
p = [0] * n # p[i]表示以i为中心的回文半径
center = right = 0
max_len = start = 0
for i in range(n):
if i < right:
p[i] = min(right - i, p[2 * center - i])
# 中心扩展
while (i - p[i] - 1 >= 0 and i + p[i] + 1 < n and
t[i - p[i] - 1] == t[i + p[i] + 1]):
p[i] += 1
# 更新最右回文边界
if i + p[i] > right:
center = i
right = i + p[i]
# 更新最长回文子串
if p[i] > max_len:
max_len = p[i]
start = (i - max_len) // 2
return s[start:start + max_len]
中心扩展算法
算法思想
- 枚举每个可能的回文中心
- 向两边扩展，直到不能形成回文
- 需要分别处理奇数和偶数长度的回文串
时间复杂度
- 时间复杂度：
- 空间复杂度：
应用场景
- 回文子串判断
- 最长回文子串查找
- 回文子序列统计
- DNA序列分析
- 文本特征提取
注意事项
- 特殊字符的处理
- 边界条件的判断
- 奇偶长度的统一
- 空串的处理
- 字符串长度的限制
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
查看12道真题和解析
