1. 题意

给定一个由若干整数组成的数组 nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。

2. 题解

利用$kmp$中的$next$数组性质，我们可以求出$nums$中的最长公共

前缀后缀。如果要是由一个子数组循环组成的话，那么必然有$next[sz]\%(n-next[sz])=0$。

为什么满足这个性质就能说明是由子数组循环若干次组成的呢？

我们假设上面的条件成立，且将字符串每$k=n-next[n]$个划为一组。那么字符串可以表示为$b_1\cdots b_{n/k}$。

由于$k=n-next[n]$, 因此串$b_0{b}_1\cdots b_{n/k-1}=b_2\cdots b_{n/k}$（最长公共前后缀）。进而
$$\begin{gathered} b_1=b_2 \\ {b}_2=b_3 \\ \cdots \\ {b}_{n/k-1}=b_{n/k} \end{gathered}$$
因此
$$b_1=b_2=\cdots =b_{n/k}$$
串为循环串。

例如

s     :    a  b c a b c a b c
next  :    -1 0 0 0 1 2 3 4 5 6
n = 9
next[n] = 6
n -next[n] = 3
6 = 2 x 3

• 代码

#include <iostream>
#include <string>
#include <vector>int main()
{int n;std::cin >> n;std::vector<int> a(n, 0);for ( int i = 0; i < n; ++i) {std::cin >> a[i];}std::vector<int> next( n + 1, 0);int j = -1;int i =  0;next[0] = -1;while ( i < n) {if ( j == -1 || a[i] == a[j]) {++i;++j;next[i] = j;}else {j = next[j];}}int k = n;if ( (next[n] >= (n - next[n])) && (next[n] % (n - next[n]) == 0)) {k = n - next[n];}for (int i = 0; i < k; ++i) {if ( i )std::cout << " ";std::cout << a[i];}return 0;
}