【题解KMP-1】OD260. 最小循环子数组
题目描述
给定一个由若干整数组成的数组nums，请检查数组是否是由某个子数组重复循环拼接而成，请输出这个最小的子数组。
输入描述
第一行输入数组中元素个数n，1 ≤ n ≤ 100000
第二行输入数组的数字序列nums，以空格分割，0 ≤ nums[i] < 10
输出描述
输出最小的子数组的数字序列，以空格分割；
备注
数组本身是其最大的子数组，循环1次可生成的自身；
用例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理解之：前缀子串，后缀子串，前后缀最长公共子串
121121121的前缀子串【含有第一个字符的所有子串（长度<n）】有:{1,12,121,1211,12112,121121,1211211,12112112}
121121121的后缀子串【含有最后1个字符的所有子串（长度<n）】有:{1,21,121,1121,21121,121121,1121121,21121121}
相同的子串有1, 121，121121共3个，其中最长的是121121。
答案需要的：重复循环的最小的子字符串【如果存在】= 字符串s(121121121)的长度-121121的长度=3.
所以问题变成了：找字符串121121121所有前缀子串和所有后缀子串 的【最长公共子串】的长度。
这就需要用到动态规划最擅长的功能了，由简单推复杂，由小问题推规模更大的问题。
字符串121121121更小规模的问题是：1=>12=>121=>1211=>12112=>121121=>1211211=>12112112.
1）字符串1:
前缀子串：{}， 后缀子串：{}=》最长公共子串的长度=0。
2）字符串12:
前缀子串：{1}，后缀子串：{2}=》最长公共子串的长度=0
3）字符串121
前缀子串：{1,12}，后缀子串：{1,21}=》最长公共子串{1}的长度=1
4）字符串1211
前缀子串：{1,12,121}，后缀子串：{1,11,211}=》最长公共子串{1}的长度=1
5）字符串12112
前缀子串：{1,12,121,1211}，后缀子串：{2,12,,112,2112}=》最长公共子串{12}的长度=2
KMP理解之：next[] 数组以及生成方式
数组int[] next保存以上以i【0-8】位置结尾的字符串对应的前后缀公共子串长度。所以121121121的next数组值看上图是{0,0,1,1,2,3,4,5,6}。
下面代码是求字符串next数组的方法：
public static int[] KMPnext(int[] dest){
int[] next = new int[dest.length];
next[0] = 0; //i=0时一定是0
for(int i = 1,j = 0; i < dest.length; i++){
while(j > 0 && dest[j] != dest[i]) j = next[j - 1]; //注意是while，不是if
if(dest[i] == dest[j]) j++; //动态规划体现在这，在j-1的答案基础上长度继续增加。
next[i] = j;
}
return next;
}
以上代码有几个问题：
1）next[0]为何是0？
next[0]对应上面长度为1的字符串，前后子串都是空，所以公共子串长度一定是0.
2）for(int i = 1,j = 0; i < dest.length; i++){ 为何i从1开始但是j从0开始？
因为i是0，next值已经是0，所以从i=1开始，j默认从0开始进行匹配。i是原字符串对应的匹配位置，j是匹配字符串对应的位置，此处原字符串和匹配字符串都是s, 自己匹配自己。
比如：12对应匹配i=1，j=0，i=1和j=0字符2和1不同，next[1]=0;
121对应匹配i=2，j=0, i=2和j=0 字符1和1相同， next[2]=1;
1211对应匹配i=3，j=1, i=3和j=1 字符1和2不相同， j=next[j-1]=next[0]=0;
if(dest[i] == dest[j]) 此处i=3和j=0字符相同，j++所以j=1，next[3]=1;
12112对应匹配i=4，j=1, ,i=4和j=1 字符2和2相同，j++所以j=1，next[4]=2; /
for循环的含义：理想情况下s在i位置如果和 s在j位置匹配，如果s在i+1和j+1仍然匹配，则next[i+1]=next[i]+1，
（代码对应 if(dest[i] == dest[j]) j++;）【动态规划 匹配处理】next[i]=j;
否则j回退到next[j-1]。 所以对KMP算法最有效率的情况是 匹配的字符串每个子串的 前后缀子串 最长公共子串长度>0
3) while(j > 0 && dest[j] != dest[i]) j = next[j - 1]； 为何是while而不是if。
字符串“abababe”，的next在if 的情况next值：[0, 0, 1, 2, 3, 4, 2]，在while的next值： [0, 0, 1, 2, 3, 4, 0]
4) 为何while循环：j>0。因为上面j=next[j-1]，j-1就要求j>0才能这样写
5) 为何： j = next[j - 1]。
例子1:abababe,i=6的时候字符e，和j=4字符a不匹配，a之前的字符串abab的最长公共后缀字符串ab得被自己的的最长公共前缀字符串替换。上图abab的公共后缀ab被公共前缀ab替换之后成ab
例子2:abceabcd。 0 0 0 0 1 2 3 匹配最后1个d的时候，i=7，j=3，不等e之前的字符串abc最长公共前后缀长度是0，所以j=next[j-1]=next[2]=0.
例子3:abcabcabe。c之前的abcab的公共后缀ab被其公共前缀替换替换成ab
例子4:下图：abceabce和abceabcd，之间e和d不匹配了，d之前字符串abceabc的最长公共前后缀是abc，j=next[j-1]此时刚好把最长公共前缀向后挪动1个重叠位置。目标是为了e和d不匹配位置之前字符串【abceabc】的 最长公共前缀匹配 替换 最长公共后缀匹配。next[j-1]的位置刚好对应最长公共前缀的长度。j=3；
总结：KMP算法其实是一种动态规划算法，主要体现在next数组的构建上。
OD260. 最小循环子数组的代码
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.valueOf(br.readLine());
int[] a=Arrays.stream(br.readLine().split(" ")).mapToInt(k->Integer.valueOf(k)).toArray();
int[] next=KMPnext(a);
int m=next[n-1];
int len=n%(n-m)==0?(n-m):n; //需要检测n是否刚好满足最短子串的重叠，不满足长度是n
StringJoiner sj=new StringJoiner(" ");
for (int i=0;i<len;i++) sj.add(a[i]+"");
System.out.println(sj);
}
public static int[] KMPnext(int[] dest){ //模板代码
int[] next = new int[dest.length];
next[0] = 0;
for(int i = 1,j = 0; i < dest.length; i++){
if(j > 0 && dest[j] != dest[i]) j = next[j - 1];
if(dest[i] == dest[j]) j++;
next[i] = j;
}
return next;
}
同系列题目：
动态规划相关算法笔试题
查看4道真题和解析