1000 lines
29 KiB
Markdown
Executable File
1000 lines
29 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
> KMP算法还能干这个
|
||
|
||
# 459.重复的子字符串
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/repeated-substring-pattern/)
|
||
|
||
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
|
||
|
||
示例 1:
|
||
* 输入: "abab"
|
||
* 输出: True
|
||
* 解释: 可由子字符串 "ab" 重复两次构成。
|
||
|
||
示例 2:
|
||
* 输入: "aba"
|
||
* 输出: False
|
||
|
||
示例 3:
|
||
* 输入: "abcabcabcabc"
|
||
* 输出: True
|
||
* 解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[字符串这么玩，可有点难度！ | LeetCode：459.重复的子字符串](https://www.bilibili.com/video/BV1cg41127fw)，相信结合视频再看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
## 思路
|
||
|
||
|
||
暴力的解法， 就是一个for循环获取 子串的终止位置， 然后判断子串是否能重复构成字符串，又嵌套一个for循环，所以是O(n^2)的时间复杂度。
|
||
|
||
有的同学可以想，怎么一个for循环就可以获取子串吗？ 至少得一个for获取子串起始位置，一个for获取子串结束位置吧。
|
||
|
||
其实我们只需要判断，以第一个字母为开始的子串就可以，所以一个for循环获取子串的终止位置就行了。 而且遍历的时候 都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。
|
||
|
||
暴力的解法，这里就不详细讲解了。
|
||
|
||
主要讲一讲移动匹配 和 KMP两种方法。
|
||
|
||
### 移动匹配
|
||
|
||
当一个字符串s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是这样的：
|
||
|
||
|
||
|
||
也就是由前后相同的子串组成。
|
||
|
||
那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前面的子串做后串，就一定还能组成一个s，如图：
|
||
|
||
|
||
|
||
|
||
当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，**要刨除 s + s 的首字符和尾字符**，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
|
||
|
||
|
||
以上证明的充分性，接下来证明必要性：
|
||
|
||
如果有一个字符串s，在 s + s 拼接后， 不算首尾字符，如果能凑成s字符串，说明s 一定是重复子串组成。
|
||
|
||
如图，字符串s，图中数字为数组下标，在 s + s 拼接后， 不算首尾字符，中间凑成s字符串。 （图中数字为数组下标）
|
||
|
||
|
||
|
||
图中，因为中间拼接成了s，根据红色框 可以知道 s[4] = s[0]， s[5] = s[1]， s[0] = s[2], s[1] = s[3] s[2] = s[4] ,s[3] = s[5]
|
||
|
||
|
||
|
||
以上相等关系我们串联一下：
|
||
|
||
s[4] = s[0] = s[2]
|
||
|
||
s[5] = s[1] = s[3]
|
||
|
||
|
||
即：s[4],s[5] = s[0],s[1] = s[2],s[3]
|
||
|
||
**说明这个字符串，是由 两个字符 s[0] 和 s[1] 重复组成的**！
|
||
|
||
这里可以有录友想，凭什么就是这样组成的s呢，我换一个方式组成s 行不行，如图：
|
||
|
||
|
||
|
||
s[3] = s[0]，s[4] = s[1] ，s[5] = s[2]，s[0] = s[3]，s[1] = s[4]，s[2] = s[5]
|
||
|
||
以上相等关系串联：
|
||
|
||
s[3] = s[0]
|
||
|
||
s[1] = s[4]
|
||
|
||
s[2] = s[5]
|
||
|
||
s[0] s[1] s[2] = s[3] s[4] s[5]
|
||
|
||
和以上推导过程一样，最后可以推导出，这个字符串是由 s[0] ，s[1] ，s[2] 重复组成。
|
||
|
||
如果是这样的呢，如图：
|
||
|
||
|
||
|
||
s[1] = s[0]，s[2] = s[1] ，s[3] = s[2]，s[4] = s[3]，s[5] = s[4]，s[0] = s[5]
|
||
|
||
以上相等关系串联
|
||
|
||
s[0] = s[1] = s[2] = s[3] = s[4] = s[5]
|
||
|
||
最后可以推导出，这个字符串是由 s[0] 重复组成。
|
||
|
||
以上 充分和必要性都证明了，所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
|
||
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
bool repeatedSubstringPattern(string s) {
|
||
string t = s + s;
|
||
t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
|
||
if (t.find(s) != std::string::npos) return true; // r
|
||
return false;
|
||
}
|
||
};
|
||
```
|
||
* 时间复杂度: O(n)
|
||
* 空间复杂度: O(1)
|
||
|
||
不过这种解法还有一个问题，就是 我们最终还是要判断 一个字符串（s + s）是否出现过 s 的过程，大家可能直接用contains，find 之类的库函数， 却忽略了实现这些函数的时间复杂度（暴力解法是m * n，一般库函数实现为 O(m + n)）。
|
||
|
||
如果我们做过 [28.实现strStr](https://programmercarl.com/0028.实现strStr.html) 题目的话，其实就知道，**实现一个 高效的算法来判断 一个字符串中是否出现另一个字符串是很复杂的**，这里就涉及到了KMP算法。
|
||
|
||
### KMP
|
||
|
||
#### 为什么会使用KMP
|
||
|
||
以下使用KMP方式讲解，强烈建议大家先把以下两个视频看了，理解KMP算法，再来看下面讲解，否则会很懵。
|
||
|
||
* [视频讲解版：帮你把KMP算法学个通透！（理论篇）](https://www.bilibili.com/video/BV1PD4y1o7nd/)
|
||
* [视频讲解版：帮你把KMP算法学个通透！（求next数组代码篇）](https://www.bilibili.com/video/BV1M5411j7Xx)
|
||
* [文字讲解版：KMP算法](https://programmercarl.com/0028.实现strStr.html)
|
||
|
||
在一个串中查找是否出现过另一个串，这是KMP的看家本领。那么寻找重复子串怎么也涉及到KMP算法了呢？
|
||
|
||
KMP算法中next数组为什么遇到字符不匹配的时候可以找到上一个匹配过的位置继续匹配，靠的是有计算好的前缀表。
|
||
|
||
前缀表里，统计了各个位置为终点字符串的最长相同前后缀的长度。
|
||
|
||
那么 最长相同前后缀和重复子串的关系又有什么关系呢。
|
||
|
||
可能很多录友又忘了 前缀和后缀的定义，再回顾一下：
|
||
|
||
* 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
|
||
* 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
|
||
|
||
#### 充分性证明
|
||
|
||
如果一个字符串s是由重复子串组成，那么 最长相等前后缀不包含的子串一定是字符串s的最小重复子串。
|
||
|
||
如果s 是由最小重复子串p组成，即 s = n * p
|
||
|
||
那么相同前后缀可以是这样：
|
||
|
||
|
||
|
||
也可以是这样：
|
||
|
||
|
||
|
||
最长的相等前后缀，也就是这样：
|
||
|
||
|
||
|
||
这里有录友就想：如果字符串s 是由最小重复子串p组成，最长相等前后缀就不能更长一些？ 例如这样：
|
||
|
||
|
||
|
||
如果这样的话，因为前后缀要相同，所以 p2 = p1，p3 = p2，如图：
|
||
|
||
|
||
|
||
p2 = p1，p3 = p2 即： p1 = p2 = p3
|
||
|
||
说明 p = p1 * 3。
|
||
|
||
这样p 就不是最小重复子串了，不符合我们定义的条件。
|
||
|
||
所以，**如果这个字符串s是由重复子串组成，那么最长相等前后缀不包含的子串是字符串s的最小重复子串**。
|
||
|
||
#### 必要性证明
|
||
|
||
以上是充分性证明，以下是必要性证明：
|
||
|
||
**如果 最长相等前后缀不包含的子串是字符串s的最小重复子串， 那么字符串s一定由重复子串组成吗**？
|
||
|
||
最长相等前后缀不包含的子串已经是字符串s的最小重复子串，那么字符串s一定由重复子串组成，这个不需要证明了。
|
||
|
||
关键是要证明：最长相等前后缀不包含的子串什么时候才是字符串s的最小重复子串呢。
|
||
|
||
情况一， 最长相等前后缀不包含的子串的长度 比 字符串s的一半的长度还大，那一定不是字符串s的重复子串，如图：
|
||
|
||
|
||
|
||
图中：前后缀不包含的子串的长度 大于 字符串s的长度的 二分之一
|
||
|
||
--------------
|
||
|
||
情况二，最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除，如图：
|
||
|
||
|
||
|
||
步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：，s[0]s[1]与s[2]s[3]相同 。
|
||
|
||
步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。
|
||
|
||
步骤三： 因为 这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。
|
||
|
||
步骤四：循环往复。
|
||
|
||
所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。
|
||
|
||
可以推出，在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串。
|
||
|
||
即 s[0]s[1] 是最小重复子串
|
||
|
||
|
||
以上推导中，录友可能想，你怎么知道 s[0] 和 s[1] 就不相同呢？ s[0] 为什么就不能是最小重复子串。
|
||
|
||
如果 s[0] 和 s[1] 也相同，同时 s[0]s[1]与s[2]s[3]相同，s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同，那么这个字符串就是有一个字符构成的字符串。
|
||
|
||
那么它的最长相同前后缀，就不是上图中的前后缀，而是这样的的前后缀：
|
||
|
||
|
||
|
||
录友可能再问，由一个字符组成的字符串，最长相等前后缀凭什么就是这样的。
|
||
|
||
有这种疑惑的录友，就是还不知道 最长相等前后缀 是怎么算的。
|
||
|
||
可以看这里：[KMP讲解](https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html)，再去回顾一下。
|
||
|
||
或者说，自己举个例子，`aaaaaa`，这个字符串，他的最长相等前后缀是什么？
|
||
|
||
同上以上推导，最长相等前后缀不包含的子串的长度只要被 字符串s的长度整除，最长相等前后缀不包含的子串一定是最小重复子串。
|
||
|
||
----------------
|
||
|
||
**情况三，最长相等前后缀不包含的子串的长度 不被 字符串s的长度整除得情况**，如图：
|
||
|
||
|
||
|
||
|
||
步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，t[2] 与 k[2]相同。
|
||
|
||
所以 s[0] 与 s[3]相同，s[1] 与 s[4]相同，s[2] 与s[5]，即：，s[0]s[1]与s[2]s[3]相同 。
|
||
|
||
步骤二： 因为在同一个字符串位置，所以 t[3] 与 k[0]相同，t[4] 与 k[1]相同。
|
||
|
||
|
||
步骤三： 因为 这是相等的前缀和后缀，t[3] 与 k[3]相同 ，t[4]与k[5] 相同，所以，s[3]一定和s[6]相同，s[4]一定和s[7]相同，即：s[3]s[4] 与 s[6]s[7]相同。
|
||
|
||
|
||
以上推导，可以得出 s[0],s[1],s[2] 与 s[3],s[4],s[5] 相同，s[3]s[4] 与 s[6]s[7]相同。
|
||
|
||
那么 最长相等前后缀不包含的子串的长度 不被 字符串s的长度整除 ，最长相等前后缀不包含的子串就不是s的重复子串
|
||
|
||
-----------
|
||
|
||
充分条件：如果字符串s是由重复子串组成，那么 最长相等前后缀不包含的子串 一定是 s的最小重复子串。
|
||
|
||
必要条件：如果字符串s的最长相等前后缀不包含的子串 是 s最小重复子串，那么 s是由重复子串组成。
|
||
|
||
在必要条件，这个是 显而易见的，都已经假设 最长相等前后缀不包含的子串 是 s的最小重复子串了，那s必然是重复子串。
|
||
|
||
**关键是需要证明， 字符串s的最长相等前后缀不包含的子串 什么时候才是 s最小重复子串**。
|
||
|
||
同上我们证明了，当 最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除，那么不包含的子串 就是s的最小重复子串。
|
||
|
||
|
||
-------------
|
||
|
||
|
||
### 代码分析
|
||
|
||
next 数组记录的就是最长相同前后缀（ [字符串：KMP算法精讲](https://programmercarl.com/0028.实现strStr.html)）， 如果 `next[len - 1] != -1`，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。
|
||
|
||
最长相等前后缀的长度为：`next[len - 1] + 1`。(这里的next数组是以统一减一的方式计算的，因此需要+1，两种计算next数组的具体区别看这里：[字符串：KMP算法精讲](https://programmercarl.com/0028.实现strStr.html))
|
||
|
||
数组长度为：len。
|
||
|
||
`len - (next[len - 1] + 1)` 是最长相等前后缀不包含的子串的长度。
|
||
|
||
如果`len % (len - (next[len - 1] + 1)) == 0` ，则说明数组的长度正好可以被 最长相等前后缀不包含的子串的长度 整除 ，说明该字符串有重复的子字符串。
|
||
|
||
### 打印数组
|
||
|
||
**强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法**
|
||
|
||
如图：
|
||
|
||
|
||
|
||
`next[len - 1] = 7`，`next[len - 1] + 1 = 8`，8就是此时字符串asdfasdfasdf的最长相同前后缀的长度。
|
||
|
||
`(len - (next[len - 1] + 1))` 也就是： 12(字符串的长度) - 8(最长公共前后缀的长度) = 4， 为最长相同前后缀不包含的子串长度
|
||
|
||
|
||
4可以被 12(字符串的长度) 整除，所以说明有重复的子字符串（asdf）。
|
||
|
||
### 代码实现
|
||
|
||
C++代码如下：（这里使用了前缀表统一减一的实现方式）
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
void getNext (int* next, const string& s){
|
||
next[0] = -1;
|
||
int j = -1;
|
||
for(int i = 1;i < s.size(); i++){
|
||
while(j >= 0 && s[i] != s[j + 1]) {
|
||
j = next[j];
|
||
}
|
||
if(s[i] == s[j + 1]) {
|
||
j++;
|
||
}
|
||
next[i] = j;
|
||
}
|
||
}
|
||
bool repeatedSubstringPattern (string s) {
|
||
if (s.size() == 0) {
|
||
return false;
|
||
}
|
||
int next[s.size()];
|
||
getNext(next, s);
|
||
int len = s.size();
|
||
if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
|
||
return true;
|
||
}
|
||
return false;
|
||
}
|
||
};
|
||
```
|
||
* 时间复杂度: O(n)
|
||
* 空间复杂度: O(n)
|
||
|
||
|
||
前缀表（不减一）的C++代码实现：
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
void getNext (int* next, const string& s){
|
||
next[0] = 0;
|
||
int j = 0;
|
||
for(int i = 1;i < s.size(); i++){
|
||
while(j > 0 && s[i] != s[j]) {
|
||
j = next[j - 1];
|
||
}
|
||
if(s[i] == s[j]) {
|
||
j++;
|
||
}
|
||
next[i] = j;
|
||
}
|
||
}
|
||
bool repeatedSubstringPattern (string s) {
|
||
if (s.size() == 0) {
|
||
return false;
|
||
}
|
||
int next[s.size()];
|
||
getNext(next, s);
|
||
int len = s.size();
|
||
if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
|
||
return true;
|
||
}
|
||
return false;
|
||
}
|
||
};
|
||
```
|
||
* 时间复杂度: O(n)
|
||
* 空间复杂度: O(n)
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### Java：
|
||
|
||
（版本一） 前缀表 减一
|
||
|
||
```java
|
||
class Solution {
|
||
public boolean repeatedSubstringPattern(String s) {
|
||
if (s.equals("")) return false;
|
||
|
||
int len = s.length();
|
||
// 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
|
||
s = " " + s;
|
||
char[] chars = s.toCharArray();
|
||
int[] next = new int[len + 1];
|
||
|
||
// 构造 next 数组过程，j从0开始(空格)，i从2开始
|
||
for (int i = 2, j = 0; i <= len; i++) {
|
||
// 匹配不成功，j回到前一位置 next 数组所对应的值
|
||
while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
|
||
// 匹配成功，j往后移
|
||
if (chars[i] == chars[j + 1]) j++;
|
||
// 更新 next 数组的值
|
||
next[i] = j;
|
||
}
|
||
|
||
// 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
|
||
if (next[len] > 0 && len % (len - next[len]) == 0) {
|
||
return true;
|
||
}
|
||
return false;
|
||
}
|
||
}
|
||
```
|
||
|
||
（版本二） 前缀表 不减一
|
||
|
||
```java
|
||
/*
|
||
* 充分条件：如果字符串s是由重复子串组成的，那么它的最长相等前后缀不包含的子串一定是s的最小重复子串。
|
||
* 必要条件：如果字符串s的最长相等前后缀不包含的子串是s的最小重复子串，那么s必然是由重复子串组成的。
|
||
* 推得：当字符串s的长度可以被其最长相等前后缀不包含的子串的长度整除时，不包含的子串就是s的最小重复子串。
|
||
*
|
||
* 时间复杂度：O(n)
|
||
* 空间复杂度：O(n)
|
||
*/
|
||
class Solution {
|
||
public boolean repeatedSubstringPattern(String s) {
|
||
// if (s.equals("")) return false;
|
||
// 边界判断（可以去掉，因为题目给定范围是1 <= s.length <= 10^4）
|
||
int n = s.length();
|
||
|
||
// Step 1.构建KMP算法的前缀表
|
||
int[] next = new int[n]; // 前缀表的值表示 以该位置结尾的字符串的最长相等前后缀的长度
|
||
int j = 0;
|
||
next[0] = 0;
|
||
for (int i = 1; i < n; i++) {
|
||
while (j > 0 && s.charAt(i) != s.charAt(j)) // 只要前缀后缀还不一致，就根据前缀表回退j直到起点为止
|
||
j = next[j - 1];
|
||
if (s.charAt(i) == s.charAt(j))
|
||
j++;
|
||
next[i] = j;
|
||
}
|
||
|
||
// Step 2.判断重复子字符串
|
||
if (next[n - 1] > 0 && n % (n - next[n - 1]) == 0) { // 当字符串s的长度可以被其最长相等前后缀不包含的子串的长度整除时
|
||
return true; // 不包含的子串就是s的最小重复子串
|
||
} else {
|
||
return false;
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
### Python：
|
||
|
||
（版本一） 前缀表 减一
|
||
```python
|
||
class Solution:
|
||
def repeatedSubstringPattern(self, s: str) -> bool:
|
||
if len(s) == 0:
|
||
return False
|
||
nxt = [0] * len(s)
|
||
self.getNext(nxt, s)
|
||
if nxt[-1] != -1 and len(s) % (len(s) - (nxt[-1] + 1)) == 0:
|
||
return True
|
||
return False
|
||
|
||
def getNext(self, nxt, s):
|
||
nxt[0] = -1
|
||
j = -1
|
||
for i in range(1, len(s)):
|
||
while j >= 0 and s[i] != s[j+1]:
|
||
j = nxt[j]
|
||
if s[i] == s[j+1]:
|
||
j += 1
|
||
nxt[i] = j
|
||
return nxt
|
||
```
|
||
|
||
（版本二） 前缀表 不减一
|
||
|
||
```python
|
||
class Solution:
|
||
def repeatedSubstringPattern(self, s: str) -> bool:
|
||
if len(s) == 0:
|
||
return False
|
||
nxt = [0] * len(s)
|
||
self.getNext(nxt, s)
|
||
if nxt[-1] != 0 and len(s) % (len(s) - nxt[-1]) == 0:
|
||
return True
|
||
return False
|
||
|
||
def getNext(self, nxt, s):
|
||
nxt[0] = 0
|
||
j = 0
|
||
for i in range(1, len(s)):
|
||
while j > 0 and s[i] != s[j]:
|
||
j = nxt[j - 1]
|
||
if s[i] == s[j]:
|
||
j += 1
|
||
nxt[i] = j
|
||
return nxt
|
||
```
|
||
|
||
|
||
（版本三） 使用 find
|
||
|
||
```python
|
||
class Solution:
|
||
def repeatedSubstringPattern(self, s: str) -> bool:
|
||
n = len(s)
|
||
if n <= 1:
|
||
return False
|
||
ss = s[1:] + s[:-1]
|
||
print(ss.find(s))
|
||
return ss.find(s) != -1
|
||
```
|
||
|
||
（版本四） 暴力法
|
||
|
||
```python
|
||
class Solution:
|
||
def repeatedSubstringPattern(self, s: str) -> bool:
|
||
n = len(s)
|
||
if n <= 1:
|
||
return False
|
||
|
||
substr = ""
|
||
for i in range(1, n//2 + 1):
|
||
if n % i == 0:
|
||
substr = s[:i]
|
||
if substr * (n//i) == s:
|
||
return True
|
||
|
||
return False
|
||
```
|
||
|
||
### Go：
|
||
|
||
这里使用了前缀表统一减一的实现方式
|
||
|
||
```go
|
||
func repeatedSubstringPattern(s string) bool {
|
||
n := len(s)
|
||
if n == 0 {
|
||
return false
|
||
}
|
||
next := make([]int, n)
|
||
j := -1
|
||
next[0] = j
|
||
for i := 1; i < n; i++ {
|
||
for j >= 0 && s[i] != s[j+1] {
|
||
j = next[j]
|
||
}
|
||
if s[i] == s[j+1] {
|
||
j++
|
||
}
|
||
next[i] = j
|
||
}
|
||
// next[n-1]+1 最长相同前后缀的长度
|
||
if next[n-1] != -1 && n%(n-(next[n-1]+1)) == 0 {
|
||
return true
|
||
}
|
||
return false
|
||
}
|
||
```
|
||
|
||
前缀表（不减一）的代码实现
|
||
|
||
```go
|
||
func repeatedSubstringPattern(s string) bool {
|
||
n := len(s)
|
||
if n == 0 {
|
||
return false
|
||
}
|
||
j := 0
|
||
next := make([]int, n)
|
||
next[0] = j
|
||
for i := 1; i < n; i++ {
|
||
for j > 0 && s[i] != s[j] {
|
||
j = next[j-1]
|
||
}
|
||
if s[i] == s[j] {
|
||
j++
|
||
}
|
||
next[i] = j
|
||
}
|
||
// next[n-1] 最长相同前后缀的长度
|
||
if next[n-1] != 0 && n%(n-next[n-1]) == 0 {
|
||
return true
|
||
}
|
||
return false
|
||
}
|
||
```
|
||
|
||
移动匹配
|
||
|
||
```go
|
||
func repeatedSubstringPattern(s string) bool {
|
||
if len(s) == 0 {
|
||
return false
|
||
}
|
||
t := s + s
|
||
return strings.Contains(t[1:len(t)-1], s)
|
||
}
|
||
```
|
||
|
||
### JavaScript:
|
||
|
||
> 前缀表统一减一
|
||
|
||
```javascript
|
||
/**
|
||
* @param {string} s
|
||
* @return {boolean}
|
||
*/
|
||
var repeatedSubstringPattern = function (s) {
|
||
if (s.length === 0)
|
||
return false;
|
||
|
||
const getNext = (s) => {
|
||
let next = [];
|
||
let j = -1;
|
||
|
||
next.push(j);
|
||
|
||
for (let i = 1; i < s.length; ++i) {
|
||
while (j >= 0 && s[i] !== s[j + 1])
|
||
j = next[j];
|
||
if (s[i] === s[j + 1])
|
||
j++;
|
||
next.push(j);
|
||
}
|
||
|
||
return next;
|
||
}
|
||
|
||
let next = getNext(s);
|
||
|
||
if (next[next.length - 1] !== -1 && s.length % (s.length - (next[next.length - 1] + 1)) === 0)
|
||
return true;
|
||
return false;
|
||
};
|
||
```
|
||
|
||
> 前缀表统一不减一
|
||
|
||
```javascript
|
||
/**
|
||
* @param {string} s
|
||
* @return {boolean}
|
||
*/
|
||
var repeatedSubstringPattern = function (s) {
|
||
if (s.length === 0)
|
||
return false;
|
||
|
||
const getNext = (s) => {
|
||
let next = [];
|
||
let j = 0;
|
||
|
||
next.push(j);
|
||
|
||
for (let i = 1; i < s.length; ++i) {
|
||
while (j > 0 && s[i] !== s[j])
|
||
j = next[j - 1];
|
||
if (s[i] === s[j])
|
||
j++;
|
||
next.push(j);
|
||
}
|
||
|
||
return next;
|
||
}
|
||
|
||
let next = getNext(s);
|
||
|
||
if (next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0)
|
||
return true;
|
||
return false;
|
||
};
|
||
```
|
||
|
||
> 正则匹配
|
||
```javascript
|
||
/**
|
||
* @param {string} s
|
||
* @return {boolean}
|
||
*/
|
||
var repeatedSubstringPattern = function(s) {
|
||
let reg = /^(\w+)\1+$/
|
||
return reg.test(s)
|
||
};
|
||
```
|
||
> 移动匹配
|
||
```javascript
|
||
/**
|
||
* @param {string} s
|
||
* @return {boolean}
|
||
*/
|
||
var repeatedSubstringPattern = function (s) {
|
||
let ss = s + s;
|
||
return ss.substring(1, ss.length - 1).includes(s);
|
||
};
|
||
```
|
||
|
||
### TypeScript:
|
||
|
||
> 前缀表统一减一
|
||
|
||
```typescript
|
||
function repeatedSubstringPattern(s: string): boolean {
|
||
function getNext(str: string): number[] {
|
||
let next: number[] = [];
|
||
let j: number = -1;
|
||
next[0] = j;
|
||
for (let i = 1, length = str.length; i < length; i++) {
|
||
while (j >= 0 && str[i] !== str[j + 1]) {
|
||
j = next[j];
|
||
}
|
||
if (str[i] === str[j + 1]) {
|
||
j++;
|
||
}
|
||
next[i] = j;
|
||
}
|
||
return next;
|
||
}
|
||
|
||
let next: number[] = getNext(s);
|
||
let sLength: number = s.length;
|
||
let nextLength: number = next.length;
|
||
let suffixLength: number = next[nextLength - 1] + 1;
|
||
if (suffixLength > 0 && sLength % (sLength - suffixLength) === 0) return true;
|
||
return false;
|
||
};
|
||
```
|
||
|
||
> 前缀表不减一
|
||
|
||
```typescript
|
||
function repeatedSubstringPattern(s: string): boolean {
|
||
function getNext(str: string): number[] {
|
||
let next: number[] = [];
|
||
let j: number = 0;
|
||
next[0] = j;
|
||
for (let i = 1, length = str.length; i < length; i++) {
|
||
while (j > 0 && str[i] !== str[j]) {
|
||
j = next[j - 1];
|
||
}
|
||
if (str[i] === str[j]) {
|
||
j++;
|
||
}
|
||
next[i] = j;
|
||
}
|
||
return next;
|
||
}
|
||
|
||
let next: number[] = getNext(s);
|
||
let sLength: number = s.length;
|
||
let nextLength: number = next.length;
|
||
let suffixLength: number = next[nextLength - 1];
|
||
if (suffixLength > 0 && sLength % (sLength - suffixLength) === 0) return true;
|
||
return false;
|
||
};
|
||
```
|
||
|
||
### Swift:
|
||
|
||
> 前缀表统一减一
|
||
```swift
|
||
func repeatedSubstringPattern(_ s: String) -> Bool {
|
||
|
||
let sArr = Array(s)
|
||
let len = s.count
|
||
if len == 0 {
|
||
return false
|
||
}
|
||
var next = Array.init(repeating: -1, count: len)
|
||
|
||
getNext(&next,sArr)
|
||
|
||
if next.last != -1 && len % (len - (next[len-1] + 1)) == 0{
|
||
return true
|
||
}
|
||
|
||
return false
|
||
}
|
||
|
||
func getNext(_ next: inout [Int], _ str:[Character]) {
|
||
|
||
var j = -1
|
||
next[0] = j
|
||
|
||
for i in 1 ..< str.count {
|
||
|
||
while j >= 0 && str[j+1] != str[i] {
|
||
j = next[j]
|
||
}
|
||
|
||
if str[i] == str[j+1] {
|
||
j += 1
|
||
}
|
||
|
||
next[i] = j
|
||
}
|
||
}
|
||
```
|
||
|
||
> 前缀表统一不减一
|
||
```swift
|
||
func repeatedSubstringPattern(_ s: String) -> Bool {
|
||
|
||
let sArr = Array(s)
|
||
let len = sArr.count
|
||
if len == 0 {
|
||
return false
|
||
}
|
||
|
||
var next = Array.init(repeating: 0, count: len)
|
||
getNext(&next, sArr)
|
||
|
||
if next[len-1] != 0 && len % (len - next[len-1]) == 0 {
|
||
return true
|
||
}
|
||
|
||
return false
|
||
}
|
||
|
||
// 前缀表不减一
|
||
func getNext(_ next: inout [Int], _ sArr:[Character]) {
|
||
|
||
var j = 0
|
||
next[0] = 0
|
||
|
||
for i in 1 ..< sArr.count {
|
||
|
||
while j > 0 && sArr[i] != sArr[j] {
|
||
j = next[j-1]
|
||
}
|
||
|
||
if sArr[i] == sArr[j] {
|
||
j += 1
|
||
}
|
||
|
||
next[i] = j
|
||
}
|
||
}
|
||
```
|
||
|
||
### Rust:
|
||
|
||
>前缀表统一不减一
|
||
```Rust
|
||
impl Solution {
|
||
pub fn get_next(next: &mut Vec<usize>, s: &Vec<char>) {
|
||
let len = s.len();
|
||
let mut j = 0;
|
||
for i in 1..len {
|
||
while j > 0 && s[i] != s[j] {
|
||
j = next[j - 1];
|
||
}
|
||
if s[i] == s[j] {
|
||
j += 1;
|
||
}
|
||
next[i] = j;
|
||
}
|
||
}
|
||
|
||
pub fn repeated_substring_pattern(s: String) -> bool {
|
||
let s = s.chars().collect::<Vec<char>>();
|
||
let len = s.len();
|
||
if len == 0 { return false; };
|
||
let mut next = vec![0; len];
|
||
Self::get_next(&mut next, &s);
|
||
if next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0 { return true; }
|
||
return false;
|
||
}
|
||
}
|
||
```
|
||
|
||
>前缀表统一减一
|
||
|
||
```rust
|
||
impl Solution {
|
||
pub fn get_next(next_len: usize, s: &Vec<char>) -> Vec<i32> {
|
||
let mut next = vec![-1; next_len];
|
||
let mut j = -1;
|
||
for i in 1..s.len() {
|
||
while j >= 0 && s[i] != s[(j + 1) as usize] {
|
||
j = next[j as usize];
|
||
}
|
||
if s[i] == s[(j + 1) as usize] {
|
||
j += 1;
|
||
}
|
||
next[i] = j;
|
||
}
|
||
next
|
||
}
|
||
pub fn repeated_substring_pattern(s: String) -> bool {
|
||
let s_chars = s.chars().collect::<Vec<char>>();
|
||
let next = Self::get_next(s_chars.len(), &s_chars);
|
||
if next[s_chars.len() - 1] >= 0
|
||
&& s_chars.len() % (s_chars.len() - (next[s_chars.len() - 1] + 1) as usize) == 0
|
||
{
|
||
return true;
|
||
}
|
||
false
|
||
}
|
||
}
|
||
```
|
||
### C#
|
||
|
||
> 前缀表不减一
|
||
|
||
```csharp
|
||
public bool RepeatedSubstringPattern(string s)
|
||
{
|
||
if (s.Length == 0)
|
||
return false;
|
||
int[] next = GetNext(s);
|
||
int len = s.Length;
|
||
if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) return true;
|
||
return false;
|
||
}
|
||
public int[] GetNext(string s)
|
||
{
|
||
int[] next = Enumerable.Repeat(0, s.Length).ToArray();
|
||
for (int i = 1, j = 0; i < s.Length; i++)
|
||
{
|
||
while (j > 0 && s[i] != s[j])
|
||
j = next[j - 1];
|
||
if (s[i] == s[j])
|
||
j++;
|
||
next[i] = j;
|
||
}
|
||
return next;
|
||
}
|
||
```
|
||
|
||
> 移动匹配
|
||
```csharp
|
||
public bool RepeatedSubstringPattern(string s) {
|
||
string ss = (s + s).Substring(1, (s + s).Length - 2);
|
||
return ss.Contains(s);
|
||
}
|
||
```
|
||
### C
|
||
|
||
```c
|
||
// 前缀表不减一
|
||
int *build_next(char* s, int len) {
|
||
|
||
int *next = (int *)malloc(len * sizeof(int));
|
||
assert(next);
|
||
|
||
// 初始化前缀表
|
||
next[0] = 0;
|
||
|
||
// 构建前缀表表
|
||
int i = 1, j = 0;
|
||
while (i < len) {
|
||
if (s[i] == s[j]) {
|
||
j++;
|
||
next[i] = j;
|
||
i++;
|
||
} else if (j > 0) {
|
||
j = next[j - 1];
|
||
} else {
|
||
next[i] = 0;
|
||
i++;
|
||
}
|
||
}
|
||
return next;
|
||
}
|
||
|
||
bool repeatedSubstringPattern(char* s) {
|
||
|
||
int len = strlen(s);
|
||
int *next = build_next(s, len);
|
||
bool result = false;
|
||
|
||
// 检查最小重复片段能否被长度整除
|
||
if (next[len - 1]) {
|
||
result = len % (len - next[len - 1]) == 0;
|
||
}
|
||
|
||
free(next);
|
||
return result;
|
||
}
|
||
|
||
```
|
||
|
||
|