AC Log - 中心扩散
type: channel
link: https://aclog.neix.in/index.php/tag/%E4%B8%AD%E5%BF%83%E6%89%A9%E6%95%A3/
items: 最长回文子串

最长回文子串
type: item
date: 2026-01-21T15:59:51+00:00
description: 题目链接：最长回文子串给你一个字符串 s，找到 s 中最长的 回文 子串。方法一：中心扩散string longestPalindrome(string s) { int n = s.size(); if (n == 0) return ""; int bestL = 0, bestLen = 1; for (int i = 0; i < n; ++i) { int l = i - 1, r = i + 1; // 吃掉与中心相同的连续字符（处理 "aaaa" 这类） while (l >= 0 && s[l] == s[i]) --l; while (r < n && s[r] == s[i]) ++r; // 再向两边扩展 while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; } int len = r - l - 1; int start = l + 1; if (len > bestLen) { bestLen = len; bestL = start; } } return s.substr(bestL, bestLen); }方法一优化string longestPalindrome(string s) { int n = s.size(); if (n == 0) return ""; int bestL = 0, bestLen = 1; for (int i = 0; i < n; ) { int l = i, r = i; while (r + 1 < n && s[r + 1] == s[i]) ++r; // 合并重复中心 i = r + 1; // 关键：跳到下一段 // 扩展 while (l - 1 >= 0 && r + 1 < n && s[l - 1] == s[r + 1]) { --l; ++r; } int len = r - l + 1; if (len > bestLen) { bestLen = len; bestL = l; } // 可选剪枝：如果剩余长度不足以超越 bestLen if ((n - i) * 2 + 1 <= bestLen) break; } return s.substr(bestL, bestLen); }