[BOI2009] Radio Transmission 无线传输
题目描述
给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的（保证至少重复 $2$ 次）。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。
输入格式
第一行一个整数 $L$，表示给出字符串的长度。
第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。
输出格式
仅一行，表示 $s_2$ 的最短长度。
样例 #1
样例输入 #1
8
cabcabca
样例输出 #1
3
提示
样例输入输出 1 解释
对于样例，我们可以利用 $\texttt{abc}$ 不断自我连接得到 $\texttt{abcabcabcabc}$，读入的 $\texttt{cabcabca}$，是它的子串。
规模与约定
对于全部的测试点，保证 $1 < L \le 10^6$。
这道题真是一道 kmp 的好题，做完之后 kmp 完全懂了。
首先要知道 next 数组是干什么用的。 $next_i$ 的意思是在 $s_1,s_2,...,s_{i-1}$ 这几个字符中，与 $s_i$ 相等的字符的下标位置。
例如样例 kmp 初始化后
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|
| c | a | b | c | a | b | c | a |
| 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 |
看完这个表后，那么最终结果为 n-nxt[n]。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
char s[N];
int n, nxt[N];
int main()
{
cin >> n >> s + 1;
for (int i = 2, j = 0; i <= n; ++ i)
{
while (j && s[i] != s[j + 1]) j = nxt[j];
if (s[i] == s[j + 1]) ++ j;
nxt[i] = j;
}
cout << n - nxt[n];
return 0;
}