用 KMP 失败函数求最长 border，最小正周期 p = n - pi[n-1]；p 整除 n 时答案为 n/p，否则为 1。
OJ: roj
题目 ID: 1466
难度:普及
标签:字符串KMP
创建: 2026-09-30 12:33
更新: 2026-10-06 00:18
题目描述
给定若干个仅含英文字母的字符串（以单独一行 . 结束输入），对每个字符串求最大重数
思路
KMP 求失败函数得到最长 border 长度
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 12:33
# update_at: 2026-09-30 12:33
import sys
STOP = b"." # 题面的结束标记，单独占一行
def power_count(s: bytes) -> int:
"""返回 s 的最短周期的重数 len(s)//p；若最短正周期分不尽 s 则返回 1。
KMP 失败函数：pi[i] = s[:i+1] 的最长「真前缀 = 真后缀」长度。
len(s) - pi[-1] 是 s 的最小正周期，只有当它是 len(s) 的约数时周期才整分 s。
"""
n = len(s)
pi = [0] * n # 失败函数数组，与 s 等长
border = 0 # 已匹配的 border 长度，即 pi[i-1] 的滚动值
for i in range(1, n):
ch = s[i]
while border and s[border] != ch: # 失配就沿 border 链回退
border = pi[border - 1]
if s[border] == ch: # 配上了，border 变长
border += 1
pi[i] = border
p = n - border
return n // p if n % p == 0 else 1
def solve() -> None:
out: list[str] = []
for line in sys.stdin.buffer.read().split():
if line == STOP:
break # 结束行之后不再有数据
out.append(str(power_count(line)))
sys.stdout.write('\n'.join(out) + '\n')
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 00:18
* update_at: 2026-10-06 00:18
*/
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1000005; // 单串最大长度
char s[MAXN];
int pi[MAXN]; // 失败函数：pi[i] 为前缀 s[0..i] 的最长 border 长度
// 返回字符串 s[0..n-1] 的最大重复重数
int power_count(int n) {
for (int i = 0; i < n; ++i) pi[i] = 0;
int border = 0; // 当前已匹配的 border 长度
for (int i = 1; i < n; ++i) {
char ch = s[i];
while (border && s[border] != ch) // 失配则沿 border 链回退
border = pi[border - 1];
if (s[border] == ch) // 匹配成功，border 延长
++border;
pi[i] = border;
}
int p = n - border; // 最小正周期
return (n % p == 0) ? (n / p) : 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> s) {
if (s[0] == '.' && s[1] == '\0') break; // 单独一行 '.' 结束输入
int n = strlen(s);
cout << power_count(n) << '\n';
}
return 0;
}