华为OD机试 - 最小循环子数组（Java）

题目描述

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

输入描述

第一行输入数组中元素个数n，1 ≤ n ≤ 100000

第二行输入数组的数字序列nums，以空格分割，0 ≤ nums[i] < 10

输出描述

输出最小的子数组的数字序列，以空格分割；

备注

数组本身是其最大的子数组，循环1次可生成的自身；

用例

输入

9
1 2 1 1 2 1 1 2 1

输出

1 2 1

说明

数组[1,2,1,1,2,1,1,2,1] 可由子数组[1,2,1]重复循环3次拼接而成

题目解析

本题可以转化为最小重复子串问题，利用KMP算法求解。

比如，有一个字符串"abababab"，该字符串可以看成是某个子串重复多次产生的，比如这个重复子串可以是"ab"，也可以是"abab"。其中"ab"就是最小重复子串。