题解 | 密码截取

deepseek大人深刻的批评了一顿，表示明明n2能解决的问题为什么要用n3

以下是更优解法，直接以i为中心，分别搜索最长的奇数回文串和偶数回文串

时间：37ms，内存：4668KB

import sys
    
for line in sys.stdin:
    a = line.strip()
    # 中心扩展
    max_len = 0
    for i in range(len(a)):
        # 奇数回文
        max_1 = 1
        l, r = i-1, i+1
        while l >= 0 and r < len(a):
            if a[l] == a[r]:
                max_1 += 2
                l -= 1
                r += 1
            else:
                break

        # 偶数回文
        max_2 = 0
        l, r = i, i+1
        while l >= 0 and r < len(a):
            if a[l] == a[r]:
                max_2 += 2
                l -= 1
                r += 1
            else:
                break
        max_len = max(max_len, max_1, max_2)
    print(max_len)

数据量很小，直接暴力遍历就可以了

1. 判断回文，双指针处理
2. 遍历操作，注意起点终点就好了

import sys

def check_abba(s):
    i, j = 0, len(s)-1
    while i < j:
        if s[i] == s[j]:
            i += 1
            j -= 1
        else:
            return False
    return True
    
for line in sys.stdin:
    a = line.strip()
    longest = 0
    # 假设密码从begin开始
    for begin in range(len(a)):
        # 假设密码从end结束，一串密码至少有两个字符才能构成回文
        for end in range(begin+2, len(a)+1):
            if check_abba(a[begin:end]):
                longest = max(longest, end-begin)
    print(longest)

运行结果：时长1082ms，内存4760KB

尝试优化了一下，end指针从字符串末尾开始往前遍历，结果发现耗时更长了。（挠头

运行结果：时长1445ms，内存4600KB

import sys

def check_abba(s):
    i, j = 0, len(s)-1
    while i < j:
        if s[i] == s[j]:
            i += 1
            j -= 1
        else:
            return False
    return True
    
for line in sys.stdin:
    a = line.strip()
    longest = 0
    # 假设密码从begin开始
    for begin in range(len(a)):
        # 假设密码从end结束，一串密码至少有两个字符才能构成回文
        for end in range(len(a), begin+1, -1):  # 优化遍历策略，遇到最长的回文串后break，进行下一次begin的循环
            if check_abba(a[begin:end]):
                longest = max(longest, end-begin)
                break
    print(longest)