开发者社区云计算文章正文

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

2024-10-14 8

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【LeetCode 22】459.重复的子字符串

一、题意

二、思考过程

在一个串中查找是否出现过另外一个串，这是KMP的看家本领。所以这道题依然要使用到KMP。不推荐hash和暴力破解。

【重点】如下：

如果next[len-1]!=0,说明字符串有最长相同前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。
如果len%(len-(next[len-1]))==0,说明字符串有重复的子字符串。

int len=s.size();
        if(next[len-1]!=0&&len%(len-(next[len-1]))==0)
        {
            return true;
        }
        return false;

三、完整代码

class Solution {
public:
    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;
    }
    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;
        }
    }
};