当前位置：首页 > article >正文

LeetCode 459.重复的子字符串

article 2024/9/21 21:03:55

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 10^4
s 由小写英文字母组成

思路

本题有两种较好的解法。

移动匹配

首先要知道一个结论：如果一个字符串内部由重复的子串组成，那么令s+s，并且让后面的子串做前串，前面的子串做后串，就一定还能组成一个s。

在判断s+s拼接的字符串里是否出现一个s的的时候可以直接使用find()等库函数，但是要记得去除s + s的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。

KMP算法

同样也需要知道一个结论：当最长相等前后缀不包含的子串的长度可以被字符串s的长度整除，那么不包含最长相等前后缀的子串就是s的最小重复子串。

next 数组记录的就是最长相同前后缀，next数组的长度为s.size()，如果 next[s.size()-1]!=-1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。

最长相等前后缀的长度为：next[s.size()-1]（如果统一减一来计算next数组，这里需要+1）。

s.size()-next[s.size()-1]是最长相等前后缀不包含的子串的长度。

如果s.size()%(s.size() -next[s.size() - 1]) == 0 ，则说明数组的长度正好可以被不包含最长相等前后缀的子串的长度整除，说明该字符串有重复的子字符串。

代码

C++版：

方法一：

class Solution {
public:
    void getNext(int* next,string& s){
        int j=0;
        next[0]=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) {
        // KMP算法
        vector<int> next(s.size());
        getNext(&next[0],s);
        if(next[s.size()-1] && s.size()%(s.size()-next[s.size()-1])==0){
            return true;
        }
        return false;
    }
    
};

方法二：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        // 移动匹配
        string t=s+s;
        // 删除首尾字符，避免在s+s中搜索出原来的s
        t.erase(t.begin());
        t.erase(t.end() - 1);  //end()是最后一个字符的下一位
        if(t.find(s)!=s.npos){
            return true;
        }
        return false;
    }
};

Python版：

方法一：

class Solution:
    def getNext(self,next:List[int],s:str)->None:
        j=0
        next[0]=0
        for i in range(1, len(s)):
            while j>0 and s[i]!=s[j]:
                j=next[j-1]
            if s[i]==s[j]:
                j+=1
            next[i] = j
        

    def repeatedSubstringPattern(self, s: str) -> bool:
        # KMP算法
        next = [0]*len(s)
        self.getNext(next, s)
        if next[-1] != 0 and len(s) % (len(s) - next[-1]) == 0:
            return True
        return False

方法二：

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        # 移动匹配
        t = s[1:] + s[:-1] # 获取除了最后一个元素之外的所有元素
        return t.find(s) != -1