[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{abcabcabc}\)，读入的 \(\texttt{cabcabca}\)，是它的子串。
规模与约定
对于全部的测试点，保证 \(1 < L \le 10^6\)。
简要声明
可使用 \(KMP\) 或者 \(hash\) 解决
瓶颈是判断区间相等
下面用一张图简要声明
上下皆是 \(S\)，每一列都相等，只需要判断橙色部分是否相同即可
\(\mathcal{Code}\)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int n;
const ull BASE = 13331;
const int MAXN = 1e6 + 7;
ull H[MAXN], P[MAXN];
char S[MAXN];
inline ull get(int l, int r) {return H[r] - H[l - 1] * P[r - l + 1]; }
int main () {
scanf("%d%s", &n, S + 1);
P[0] = 1;
for (int i = 1; i <= n; i ++) {
H[i] = H[i - 1] * BASE + S[i];
P[i] = P[i - 1] * BASE;
}
for (int i = 1; i <= n; i ++) {
if (get(1 + i, n) == get(1, n - i))
cout << i << "\n", exit(0);
}
return 0;
}
完结撒花✿✿ヽ(°▽°)ノ✿