企业官网建设流程全解析

前言

"最长回文子串"和"周期串"是字符串算法题里的两个经典题型：前者考"如何在所有子串里找满足回文性质的最长者"，后者考"如何判断一个串是不是由某个更短的单元重复而成"。两个题放在一起讲很有意义，因为它们共享同一批基本功——回文的判定、子串与子序列的区分、以及用切片和索引高效地取一段。

先厘清两个容易被题面含糊带过的概念。第一，子串（substring）是连续的，子序列（subsequence）可以不连续。本文说的"回文子串"必须是原串里连续的一段，比如"abac"的回文子串有"aba"，但"aa"不是（它在原串里不连续）。很多题把这两个词混用，是常见的出题不严谨。

第二，"周期"在两道题里的含义不一样：严格周期要求原串正好由若干份完整单元拼成（长度能被周期整除）；"前缀周期"只要求原串是某个单元无限重复的前缀，长度不必整除。本文两种都会讲，并给出各自的判定函数。

下面所有代码基于 Python 3.8 及以上，已逐行人工推演。本机没有 Python 解释器，无法实际运行验证，请以官方文档和逻辑推演为准。

一、回文的判定

最直接的判据：正着读和反着读一样，也就是s == s[::-1]。切片[::-1]用负步长把整串反转，这一步是常数时间写法的关键——不用手写循环。

# 适用于 Python 3.8+
def is_palindrome(s):
return s == s[::-1]

print(is_palindrome("level")) # True
print(is_palindrome("level2")) # False
print(is_palindrome("")) # True 空串视为回文
print(is_palindrome("a")) # True 单字符视为回文

单字符和空串都算回文，这一点在写递归或边界时要想清楚，别漏掉。

二、最长回文子串：中心扩展

在所有回文里，长度为奇数的回文（如"aba"）中心是一个字符，长度为偶数的回文（如"abba"）中心是相邻两个字符之间的缝。于是可以枚举每一个中心，向两边扩到不相等为止，记录最长的那一段。

# 适用于 Python 3.8+
def longest_palindrome(s: str) -> str:
if not s:
return ""
start = 0 # 当前最长回文在原串里的起点
max_len = 1 # 至少有一个字符，长度 1
for i in range(len(s)):
# 两种情况：奇数长度以 i 为中心，偶数长度以 (i, i+1) 为中心
for l, r in ((i, i), (i, i + 1)):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
# 退出循环时，l 和 r 各越界一格，真正的回文是 [l+1, r-1]
cur_len = r - l - 1
if cur_len > max_len:
max_len = cur_len
start = l + 1
return s[start:start + max_len]

print(longest_palindrome("babad")) # bab
print(longest_palindrome("cbbd")) # bb
print(longest_palindrome("a")) # a
print(longest_palindrome("")) # ''

推演一下"babad"：当i = 1（字符a）做奇数扩展时，l、r从 1 出发，因为s[0] == s[2]（都是b）继续扩，再往外l = -1越界停止。此时cur_len = r - l - 1，代入l = -1、r = 3得3，对应子串s[0:3]即"bab"。偶数分支在i = 1时s[1] != s[2]，cur_len为 0，不更新。最终返回"bab"。

这个算法的复杂度是时间 O(n²)、额外空间 O(1)：中心有约 2n 个，每个中心最多扩展 n 次。存在更快的Manacher 算法，时间 O(n)，原理是用已有回文的对称性避免重复扩展；它的实现细节较多，作为入门先掌握中心扩展更稳妥。

三、周期串：严格周期

严格周期的定义是：存在长度p，使得s恰好是s[:p]重复len(s) // p次的结果，且len(s)能被p整除。最小的这样的p就是最小正周期。

# 适用于 Python 3.8+
def min_period(s: str) -> int:
"""返回使 s 为完整重复串的最小周期；空串返回 0。"""
n = len(s)
if n == 0:
return 0
for p in range(1, n + 1):
if n % p == 0 and s == s[:p] * (n // p):
return p
return n

print(min_period("abcabcabc")) # 3
print(min_period("aaaa")) # 1
print(min_period("abcd")) # 4 没有更小周期，周期就是自身

"abcabcabc"：从p = 1试起，p = 3时9 % 3 == 0，s[:3]是"abc"，重复 3 次正好等于原串，返回 3。

四、周期串：前缀周期与"是否由重复构成"

如果只要求"原串是某个单元无限重复的前缀"，长度不必整除，判定就宽松一些：

# 适用于 Python 3.8+
def min_prefix_period(s: str) -> int:
"""返回最小的 p，使 s 是 s[:p] 无限重复的前缀；空串返回 0。"""
n = len(s)
for p in range(1, n + 1):
if all(s[i] == s[i % p] for i in range(n)):
return p
return 0

print(min_prefix_period("abcab")) # 3 是 "abcabc..." 的前缀
print(min_prefix_period("abcabcab")) # 3
print(min_prefix_period("abca")) # 4 不是更短单元的重复前缀

另一道常考变体是"判断字符串能否由某个子串重复多次构成"。有一个很漂亮的等价判定：s是由重复单元构成的，当且仅当s出现在(s + s)掐掉首尾的中间部分里。

# 适用于 Python 3.8+
def is_repeated(s: str) -> bool:
if len(s) < 2:
return False
return s in (s + s)[1:-1]

print(is_repeated("abab")) # True
print(is_repeated("aba")) # False
print(is_repeated("abcabcabc")) # True

推演"abab"：s + s是"abababab"，掐掉首尾得到"bababa"，其中含子串"abab"，返回True。再看"aba"：s + s是"abaaba"，掐掉首尾得到"baab"，不含"aba"，返回False。这个判定的道理是：若s由单元u重复而成，s + s里就出现了错位一份的重叠，s会落在中间部分；反之若落在中间，就说明存在这种错位，即存在重复单元。

实战：把两类题型放进同一段流程

下面这段把回文判定、中心扩展和周期判定串起来，对一组字符串分别给出结论。

# 适用于 Python 3.8+
def analyze(s: str) -> dict:
return {
"s": s,
"palindrome": s == s[::-1],
"longest_palindrome": longest_palindrome(s),
"period": min_period(s),
"repeated": is_repeated(s),
}

for text in ["babad", "abcabcabc", "abab"]:
result = analyze(text)
print(f"{result['s']!r:>12} 回文={result['palindrome']}"
f" 最长回文子串={result['longest_palindrome']!r}"
f" 周期={result['period']} 重复构成={result['repeated']}")

三种输入的结果分别是："babad"最长回文子串是"bab"、最小周期是 5（无更小周期）；"abcabcabc"最小周期是 3、由重复单元构成；"abab"最长回文子串是"aba"或"bab"（长度 3，程序按先到者取"aba"）、最小周期是 2。

常见坑点

1. 
   
2. 把子序列当子串
3. 
   

❌ 在"abac"中把不连续的"aa"当成回文子串

✅ 子串必须连续；本串的回文子串只有"aba"、"a"、"b"、"c"这类连续片段

1. 
   
2. 漏掉偶数长度的回文
3. 
   

❌ 中心扩展只枚举单字符中心，"cbbd"会得到"b"而不是"bb"

✅ 每个位置枚举两种中心：(i, i)和(i, i + 1)

1. 
   
2. 切片终点忘记"不含"
3. 
   

❌ 循环退出后用s[l:r]直接取，把越界那一格也算进去

✅ 退出时l、r各多走一格，真正的区间是s[l + 1:r]，长度为r - l - 1

1. 
   
2. 空串和单字符没有处理
3. 
   

❌longest_palindrome("")时start、max_len逻辑崩掉

✅ 开头先if not s: return ""，并把max_len初值设为 1

1. 
   
2. 周期判定忘了整除条件
3. 
   

❌ 对"abcab"直接找"能重复拼成原串"的周期，永远找不到（它本身不是完整重复串）

✅ 严格周期要n % p == 0；只判前缀关系才用逐字符比较的宽松版本

1. 
   
2. 用 O(n) 的反转判据反复调用
3. 
   

❌ 在每个中心里都用s[l:r] == s[l:r][::-1]判回文，白做了大量切片和反转

✅ 扩展时只比较两端的单个字符s[l] == s[r]，避免每次构造新串

1. 
   
2. 以为is_repeated对空串为真
3. 
   

❌ 不判长度就调用，空串在(s + s)[1:-1]里被判成True

✅ 先if len(s) < 2: return False

1. 
   
2. 沿用 Python 2 的写法
3. 
   

❌ 用print语句、xrange、unicode

✅ Python 3 里print是函数、range本身惰性；Python 2.7 已于 2020 年 1 月 1 日 EOL

总结

这两道题的核心都不是花哨技巧，而是把边界处理干净：回文的两种中心、切片终点的"不含"、空串与单字符、以及周期定义里"整除"与否的区别。中心扩展的时间复杂度是 O(n²)，Manacher 能降到 O(n)，理解这一点比记住某个实现更重要。本文代码为人工推演，本机没有 Python 解释器，未能实际运行，落笔时请结合自己的测试再确认边界。