0459.重复的子字符串
参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
> 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。 代码如下：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;
}
};
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;
}
};
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;
}
};
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;
}
}
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
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
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
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
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
}
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
}
/**
* @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;
};
/**
* @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;
};
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;
};
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;
};
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
}
}
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
}
}
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;
}
}
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
}
}
// 前缀表不减一
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;
}
