Python算法实战：最长回文子串与周期串求解指南

一、最长回文子串求解流程

第1步：过滤非字母字符并记录原始坐标

目的：剔除数字、标点和空格，仅保留参与比对的字母，防止干扰匹配逻辑。

入口与动作：通过标准输入接口读取原始文本，遍历每个字符。当字符满足字母类型条件时，将其转为统一小写存入清洗序列，同时将该字符在原字符串中的索引追加至独立坐标列表。

重要参数：字符类型判定函数、动态增长的清洗数组与原索引数组。

可观察的完成状态：获得长度缩减的纯字母列表与一一对应的原始位置表，后续切片映射将以此为基准。

第2步：遍历组合区间并校验回文结构

目的：在清洗后的序列中找出连续且正读反读一致的子串。

入口与动作：采用双重循环确定起始索引i与终止索引j。截取对应子串后，利用反向切片进行对称性比对。若两端完全匹配则计算当前长度，并与历史最大值比较。

重要参数：全局最大长度变量、最优起止指针、布尔标识位。

可观察的完成状态：指针始终锁定最长区间，若遇等长情况则自动保留最左侧记录，避免无效覆盖。

第3步：还原原串切片并输出最终结果

目的：将清洗域的数学索引映射回原始文本，按题目要求输出带标点符号的真实片段。

入口与动作：依据记录的最优起止坐标，查询原位置表获取首尾真实下标。使用原生切片语法提取目标段落并打印。

重要参数：映射表查询操作、闭开区间调整偏移量。

可观察的完成状态：控制台准确输出原始格式的子串，符合多源数据混合环境下的输出规范。

import sys
# 读取原始输入并剥离尾部换行
raw_str = sys.stdin.readline().strip()
clean_chars = []
original_indices = []

# 构建纯净字母流与原始坐标映射
for idx, char in enumerate(raw_str):
    if char.isalpha():
        clean_chars.append(char.lower())
        original_indices.append(idx)

max_len = 0
best_start = 0
best_end = 0
n = len(clean_chars)

# 枚举所有可能子串区间
for i in range(n):
    for j in range(i + 1, n + 1):
        sub = clean_chars[i:j]
        if sub == sub[::-1]:
            current_len = j - i
            # 优先更新更长区间，等长保留左侧
            if current_len > max_len:
                max_len = current_len
                best_start = i
                best_end = j

# 映射回原串并展示结果
if max_len > 0:
    orig_start = original_indices[best_start]
    orig_end = original_indices[best_end - 1]
    print(f"{raw_str[orig_start:orig_end + 1]}")

二、最小周期串判定流程

第1步：枚举合法周期长度

目的：缩小搜索空间，确保候选周期能完整整除总串长度。

入口与动作：设定循环变量k从1递增遍历至总长度减1。在每次迭代中执行取模运算，过滤无法均匀切分的非法长度。

重要参数：目标字符串总长度、递增步长。

可观察的完成状态：锁定具备整数倍分割潜力的k值，进入内部对比环节。

第2步：分段切片并验证序列一致性

目的：确认相邻区块内容是否完全重合，排除部分匹配陷阱。

入口与动作：计算分割份数后，使用滑动窗口逐段提取长度为k的切片。依次比对当前块与下一块，一旦发现字符错位立即触发跳出。

重要参数：区间乘积下标公式、局部标志变量。

可观察的完成状态：内部循环顺利走完无分支中断，证明全串呈现严格周期性。

第3步：中断循环输出最小周期值

目的：利用贪心策略快速返回首个有效解，提升执行效率。

入口与动作：在外层循环中使用条件守卫捕获首次完整校验通过的k。赋值给结果变量后立即终止外层迭代，避免冗余计算。

重要参数：结果缓存变量、早停控制语句。

可观察的完成状态：终端打印唯一最小周期整数，符合样例输入预期。

import sys

my_str = sys.stdin.readline().strip()
min_period = 0

# 从小到大尝试周期长度
for k in range(1, len(my_str)):
    if len(my_str) % k == 0:
        is_valid = True
        # 逐段比对相邻切片
        for m in range(len(my_str) // k - 1):
            chunk_a = my_str[m * k : (m + 1) * k]
            chunk_b = my_str[(m + 1) * k : (m + 2) * k]
            if chunk_a != chunk_b:
                is_valid = False
                break
        
        if is_valid:
            min_period = k
            break  # 找到最小值即终止

print(min_period)

两种题型均依赖基础的遍历与比对思维，掌握坐标映射机制与切片逻辑可有效规避越界与索引偏移错误。日常练习时可配合调试工具逐步观察变量形态变化，熟悉后再尝试向KMP算法或中心扩展法演进。

以上就是Python算法实战中解决最长回文子串与周期串问题的详细内容，更多关于Python字符串处理与基础算法的资料请关注本站其它相关文章！