题解 | #最长对称子字符串#

题目链接

最长对称子字符串

题目描述

给定一个字符串（由数字或大小写字母组成），找出其中最长的对称子串。如果存在多个长度相同的最长对称子串，输出任意一个即可。

例如：

输入: "abbaad"
输出: "abba"
输入: "a1223a"
输出: "22"

解题思路

寻找最长回文（对称）子串，一个高效且直观的算法是中心扩展法。

该方法的核心思想是，任何一个回文串都有一个中心。这个中心可能是一个字符（对于奇数长度的回文串，如 "aba" 的中心是 "b"），也可能是两个字符之间的空隙（对于偶数长度的回文串，如 "abba" 的中心在两个 "b" 之间）。

算法流程：

遍历所有可能的中心：

对于一个长度为 $N$ 的字符串，总共有 $2N-1$ 个潜在的中心（ $N$ 个字符本身 + $N-1$ 个字符间的空隙）。我们可以通过一次循环遍历完所有这些中心。
从中心向两边扩展：
- 在循环中，对于每个索引 i，我们执行两次扩展检查：
  
  a. 奇数长度回文：以 s[i] 为中心，向两边扩展。初始时，左右指针都指向 i。
  
  b. 偶数长度回文：以 s[i] 和 s[i+1] 之间的空隙为中心，向两边扩展。初始时，左指针指向 i，右指针指向 i+1。
- 扩展的条件是：左右指针没有越界，并且它们指向的字符相同。如果满足条件，就将左指针向左移动一位，右指针向右移动一位，继续比较。
记录最长回文串：
- 在每次扩展结束后，我们都得到了以当前点为中心的最长回文串的长度。
- 我们用两个变量，start 和 maxLength，来实时记录和更新目前找到的最长回文子串的起始位置和长度。
- 如果在某次扩展后发现了一个更长的回文串，就更新 start 和 maxLength。
返回结果：
- 遍历完所有可能的中心后，start 和 maxLength 就对应了最终的最长回文子串。根据这两个值从原字符串中截取子串并返回即可。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 全局变量或通过引用/指针传递来记录最长回文串的起始和长度
int start = 0;
int max_len = 0;

void expand_from_center(const string& s, int left, int right) {
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    // 循环结束后, [left+1, right-1] 是回文串
    int current_len = right - left - 1;
    if (current_len > max_len) {
        max_len = current_len;
        start = left + 1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;

    if (s.length() < 2) {
        cout << s << endl;
        return 0;
    }
    
    max_len = 1; // 至少单个字符是回文

    for (int i = 0; i < s.length(); ++i) {
        // 奇数长度
        expand_from_center(s, i, i);
        // 偶数长度
        expand_from_center(s, i, i + 1);
    }

    cout << s.substr(start, max_len) << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    private int start = 0;
    private int maxLen = 0;

    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        
        maxLen = 1; // 默认单个字符是回文

        for (int i = 0; i < s.length(); i++) {
            // 奇数长度
            expandFromCenter(s, i, i);
            // 偶数长度
            expandFromCenter(s, i, i + 1);
        }
        return s.substring(start, start + maxLen);
    }

    private void expandFromCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        
        int currentLen = right - left - 1;
        if (currentLen > maxLen) {
            maxLen = currentLen;
            start = left + 1;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        Main solution = new Main();
        System.out.println(solution.longestPalindrome(s));
    }
}

import sys

def solve():
    try:
        s = sys.stdin.readline().strip()
        
        if not s or len(s) < 2:
            print(s)
            return

        start = 0
        max_len = 1

        def expand_from_center(left, right):
            nonlocal start, max_len
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            
            current_len = right - left - 1
            if current_len > max_len:
                max_len = current_len
                start = left + 1

        for i in range(len(s)):
            # 奇数长度
            expand_from_center(i, i)
            # 偶数长度
            expand_from_center(i, i + 1)
        
        print(s[start : start + max_len])

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：中心扩展法
时间复杂度： $\mathcal{O}(N^2)$ ，其中 $N$ 是字符串的长度。我们有 $2N-1$ 个潜在的中心，从每个中心扩展最多需要 $\mathcal{O}(N)$ 的时间。
空间复杂度： $\mathcal{O}(1)$ 。我们只使用了常数个额外的变量来存储状态。