# P4391 [BOI2009]Radio Transmission 无线传输 题解

[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;
}

完结撒花✿✿ヽ(°▽°)ノ✿