【题目来源】
洛谷：[P4391 BalticOI 2009] Radio Transmission 无线传输 - 洛谷
【题目描述】
给你一个字符串 \(s_1\)，它是由某个字符串 \(s_2\) 不断自我连接形成的（保证至少重复 \(2\) 次）。但是字符串 \(s_2\) 是不确定的，现在只想知道它的最短长度是多少。
【输入】
第一行一个整数 \(L\)，表示给出字符串的长度。
第二行给出字符串 \(s_1\) 的一个子串，全由小写字母组成。
【输出】
仅一行，表示 \(s_2\) 的最短长度。
【输入样例】
8
cabcabca
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P4391 无线传输》 #字符串# #前缀和# #KMP# #2009#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1000005; // 定义最大字符串长度char p[N]; // 模式串（从下标1开始存储）
int m; // 模式串长度
int nex[N]; // KMP算法中的next数组int main()
{// 输入模式串长度和模式串cin >> m;cin >> p + 1; // 从下标1开始存储字符串// 计算KMP算法中的next数组nex[0] = nex[1] = 0; // 初始化前两个位置for (int i = 2, j = 0; i <= m; i++) {// 当不匹配时利用next数组回退while (j && p[i] != p[j + 1]) {j = nex[j];}// 匹配成功则j增加if (p[i] == p[j + 1]) {j++;}nex[i] = j; // 记录当前位置的next值}// 输出最小循环节长度cout << m - nex[m];return 0;
}
【运行结果】
8
cabcabca
3