力扣-459题重复的子字符串（C++）- KMP

末蓝、 2022-09-11 06:16 2阅读 0赞

题目链接：[https://leetcode-cn.com/problems/repeated-substring-pattern/][https_leetcode-cn.com_problems_repeated-substring-pattern]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution {
        
    public:
        void getNext(int* next,const 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) {
        
            if(s.size()==0) return false;
    
            int next[s.size()];
            getNext(next,s);
    
            int len=s.size();
    
            //最长相等前后缀的长度为next[len-1]+1  数组长度为len
            //如果len%{len-(next[len-1]+1)}==0,则说明可以被数组的长度整除
            if(next[len-1]!=0&&len%(len-(next[len-1]))==0) return true;
            else return false;
        }
    };

[https_leetcode-cn.com_problems_repeated-substring-pattern]: https://leetcode-cn.com/problems/repeated-substring-pattern/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c988bd3252524d0292e372a5bebd25e5.png

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串——459. 重复的子字符串

1 题目描述给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。 2 题目示例示例 1: 输入: s = “abab” 输出: t

短命女/ 2023年10月08日 16:09/ 0 赞/ 23 阅读

相关 459. 重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。示例 1: 输入: "abab"

末蓝、/ 2023年10月05日 20:02/ 0 赞/ 2 阅读

相关（力扣）第1668. 最大重复子字符串

1668. 最大重复子字符串 -------------------- 题目要求：给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成

╰半夏微凉°/ 2022年11月15日 05:56/ 0 赞/ 196 阅读

相关（力扣）第459. 重复的子字符串

459. 重复的子字符串（效率不高，但是看了官方给你也是用的for循环，感觉基本一样吖）题目要求：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次

缺乏、安全感/ 2022年11月11日 05:21/ 0 赞/ 147 阅读

相关 leetcode459重复的子字符串

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

朴灿烈づ我的快乐病毒、/ 2022年10月08日 12:27/ 0 赞/ 158 阅读

相关力扣-459题重复的子字符串（C++）- KMP

题目链接：[https://leetcode-cn.com/problems/repeated-substring-pattern/][https_leetcode-cn.co

末蓝、/ 2022年09月11日 06:16/ 0 赞/ 3 阅读

相关力扣-28题实现strStr()（C++）- 字符串匹配+KMP算法

题目链接：[https://leetcode-cn.com/problems/implement-strstr/][https_leetcode-cn.com_problems

朴灿烈づ我的快乐病毒、/ 2022年09月11日 04:17/ 0 赞/ 166 阅读

相关 LeetCode459. 重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。示例 1: 输入: "abab"

青旅半醒/ 2022年05月23日 07:47/ 0 赞/ 177 阅读

相关 python—leetcode-459. 重复的子字符串

一、问题描述给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。示例 1: 输入:

谁借莪１个温暖的怀抱￠/ 2022年05月20日 00:59/ 0 赞/ 186 阅读

相关【LeetCode】459. 重复的子字符串

题目链接：[https://leetcode-cn.com/problems/repeated-substring-pattern/description/][https_le

爱被打了一巴掌/ 2022年05月08日 15:42/ 0 赞/ 201 阅读