重复的子字符串
注：本题的题解基本建立在KMP算法之上，对KMP算法不太了解的小伙伴可以参考这篇文章KMP算法及其改进图文详解
方法一：移动匹配
- 我们先来看几个可以由一个字串重复多次构成的主字符串：“aaa”，“ababab”，“abcabc”
- 可以发现满足条件主串的两个规律：
- 一定可以在其前半部分和后半部分找到相等的子串，如上面三个例子的子串“a”，子串“ab”，子串“abc”
- 交换前半部分和后半部分都相等的子串，主串仍然不变。
- 由此可以得到，如果我们将主串复制一份，再将这两个相同的串拼到一起，并去头去尾（防止查找的过程中找到原来的串和复制后的串），如果能在新串中找到和主串相等的子串，那就说明这个主串就可以由它的一个子串重复构成
- 例如字符串abcabc
实现代码
//获得Next数组 void GetNext(char *s,int *Next) { int len = strlen(s); Next[0] = -1; int i = 0; int k = -1; while(i < len - 1) { if(k == -1 || s[i] == s[k]) { k++; i++; if(s[i] == s[k]) Next[i] = Next[k]; else Next[i] = k; } else k = Next[k]; } } //判断是否可以在字符串s1中找到串s2 bool KMP(char *s1, char *s2, int *Next) //s1为主串，s2为从串 { int len1 = strlen(s1); int len2 = strlen(s2); int i = 0, j = 0; while(i < len1 && j < len2) { if(s1[i] == s2[j]) { i++; j++; } else if(j != 0) { j = Next[j]; if(j == -1) j = 0; } else i++; } if(j >= len2) return true; else return false; } bool repeatedSubstringPattern(char * s){ int i,j; int len = strlen(s); char *str = (char *)malloc(sizeof(char) * 2 * len + 1); int *Next = (int *)malloc(sizeof(int) * len); GetNext(s,Next); //获得Next数组 //将串s和其复制串合并到str中 for(i = 0; i < len; i++) str[i] = s[i]; j = i; for(i = 0; i < len; i++) str[j + i] = s[i]; str[2 * len] = '\0'; //去尾 str[2 * len - 1] = '\0'; return KMP(str + 1,s,Next); //str+1相当于去头 }
方法二：KMP
- 我们知道，KMP算法中，有Next数组保存了每个字符之前的子串的最长相等前后缀长度，那么最长相等前后缀长度和最小的重复子串有什么关系呢？
- 直接下结论：
- 如果一个字符串是由重复的子串构成，那么最长相等前后缀不包含的子串就是最小的重复子串
- 如果一个字符串没有相等前后缀，那么这个字符串一定不能由重复子串构成
- 由于本篇Next数组记录的是每个字符之前的子串的最长相等前后缀长度，因此为了判断该字符串是否具有相等的前后缀，需要在字符串的末尾再添加一个字符（随便什么字符都可以），这样，如果字符串没有相等的前后缀，那么Next[len - 1] = 0（len为Next数组大小）
- 字符串的最大相等前后缀长度为Next[len - 1]，由第一个结论可得，最小重复子串为
len - next[len - 1]，若len % (len - next[len - 1]) == 0，就说明字符串长度可以整除最小重复子串的长度，即可说明该字符串可以由重复子串构成。
实现代码
//求Next数组 void GetNext(char *s,int *Next) { int len = strlen(s); Next[0] = -1; int i = 0; int k = -1; while(i < len - 1) { if(k == -1 || s[i] == s[k]) { k++; i++; Next[i] = k; } else k = Next[k]; } } bool repeatSubstring(char* str ) { int len = strlen(str); //创建一个比原字符串大两个字符（一个随机字符，和空字符）的字符数组 char* s = (char*)malloc(sizeof(char) * (len + 2)); //将原字符串拷贝到新字符串中，并添加随机字符和空字符 strcpy(s,str); s[len] = 'a'; s[len + 1] = '\0'; //申请Next数组的内存 int *Next = (int *)malloc(sizeof(int) * (len + 1)); //得到Next数组 GetNext(s,Next); //如果该字符串由相等前后缀，并且字符串长度可以整除最小重复子串，那么就说明这个字符串可以由重复子串构成 //这里的len之所以不要减一，是因为Next的大小为len+1，我们要得到的就是Next的最后一个值，即Next[len] if(Next[len] != 0 && len % (len - Next[len]) == 0) return true; return false; }
