P4391 [BalticOI 2009] 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\le L \le 10^6$。

思路讲解

给出子串，找出最短循环节。

最大公共前后缀。

结论就是N-pi[N]。其实我也不是很懂。

不能够使用二分，因为周期并没有单调性。

这道题目 hash 怎么做？

哈希做法思路

核心观察：字符串 $s$ 的最小周期为 $p$，当且仅当 $p$ 是满足以下条件的最小正整数：

$$s_i = s_{i+p} \quad \forall\, 0 \le i < L - p$$

这等价于：$s$ 去掉前 $p$ 个字符得到的后缀，与去掉后 $p$ 个字符得到的前缀完全相同。即：

$$s[0 \ldots L-p-1] = s[p \ldots L-1]$$

用多项式哈希预处理后，每次子串比较 $O(1)$。从 $p=1$ 开始枚举，第一个满足条件的 $p$ 就是答案。总复杂度 $O(L)$。
参考代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string s;
    cin >> n >> s;

    const long long MOD1 = 1e9 + 7, BASE1 = 131;
    const long long MOD2 = 1e9 + 9, BASE2 = 137;

    vector<long long> h1(n + 1), h2(n + 1), pw1(n + 1), pw2(n + 1);
    h1[0] = h2[0] = 0;
    pw1[0] = pw2[0] = 1;
    for (int i = 0; i < n; i++) {
        h1[i + 1] = (h1[i] * BASE1 + s[i]) % MOD1;
        h2[i + 1] = (h2[i] * BASE2 + s[i]) % MOD2;
        pw1[i + 1] = pw1[i] * BASE1 % MOD1;
        pw2[i + 1] = pw2[i] * BASE2 % MOD2;
    }

    auto qry = [&](int l, int r) -> pair<long long, long long> {
        long long v1 = (h1[r + 1] - h1[l] * pw1[r - l + 1] % MOD1 + MOD1 * 2) % MOD1;
        long long v2 = (h2[r + 1] - h2[l] * pw2[r - l + 1] % MOD2 + MOD2 * 2) % MOD2;
        return {v1, v2};
    };

    for (int p = 1; p <= n; p++) {
        if (qry(0, n - p - 1) == qry(p, n - 1)) {
            cout << p << '\\n';
            return 0;
        }
    }
}

用了双哈希避免冲突。本质上和 KMP 中 $L - \pi_L$ 的经典做法等价，只是换了一种判断周期的手段。

详细解释关键观察

这其实就是把逐字符的条件"打包"成了一个子串相等的条件，是同一件事的两种说法。
逐字符展开：两个长度相同的子串相等，就是对应位置的字符全部相等。把两个子串的对应位置写出来：

前缀中的第 $i$ 个字符	后缀中的第 $i$ 个字符
$s[0]$	$s[p]$
$s[1]$	$s[p+1]$
$\vdots$	$\vdots$
$s[i]$	$s[i+p]$
$\vdots$	$\vdots$
$s[L-p-1]$	$s[L-1]$
前缀的第 $i$ 个字符是 $s[i]$，后缀的第 $i$ 个字符是 $s[i+p]$。
所以"两个子串相等"$\iff$ 每一行都对应相等 $\iff$ $s_i = s_{i+p}$ 对所有 $0 \le i < L-p$ 成立。
用例子直观感受：取 cabcabca，$p = 3$：

前缀（去掉后3个）：c a b c a
后缀（去掉前3个）：c a b c a
                    ↕ ↕ ↕ ↕ ↕
原串位置对应：     s[0]=s[3], s[1]=s[4], s[2]=s[5], s[3]=s[6], s[4]=s[7]

每个字符都和它后面第 $p$ 个字符相同，这就是"周期为 $p$"的含义。把这些逐个比较合在一起看，就是前缀和后缀相等。
两种说法完全等价，只是视角不同：一个是逐字符看，一个是整体看。

把这个列出来以后，我们就知道了周期 p 的成立条件是什么。可以通过枚举 p，非常简单的使用字符串哈希检验答案。

AC代码

https://www.luogu.com.cn/record/221541535

源代码

// Problem: P4391 [BalticOI 2009] Radio Transmission 无线传输
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4391
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
inline void init(){
	
}

inline void solve(){
	cin>>N;
	init();
	string s;
	cin>>s;
	// if(N==1) {cout<<1<<"\n";return;}
	s='#'+s;
	vector<ll> pi(N+5);
	FOR(i,1,N){
		if(i==1) continue;
		ll len=pi[i-1];
		while(true){
			if(s[i]==s[len+1]){
				pi[i]=len+1;
				break;
			}
			if(len==0) break;
			len=pi[len];
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<pi[i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	// ll ans=0;
	// FOR(i,1,N){
		// ans=max(ans,pi[i]);
	// }
	cout<<N-pi[N]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/221541535
*/

心路历程（WA，TLE，MLE……）