重复子字符串

gaishuobulao / 2023-05-06 / 原文

应用KMP算法

最长相等前后缀不包含的子串就是最小重复子串。

len=s.size();

如果len % (len - (next[len - 1] )) == 0

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环

此图为-1，如果从0开始则全部加1

class Solution {
public:
            void getnext(int *next,const string& s)
        {
            int j=0;//第一步，初始化
            next[0]=j;

            for(int i=1;i<s.size();i++)
            {
                while(j>0 && s[i]!=s[j])//第二步，不相等则回退
                {
                    j=next[j-1];
                }

                if(s[i]==s[j])//第三步，相等则加1
                {
                    j++;
                }

                next[i]=j;
            }
        }

    bool repeatedSubstringPattern(string s) {
        int len=s.size();
        int next[len];

        getnext(next,s);

        if(next[len-1]!=0 && len % (len-(next[len-1]))==0)
        {
            return true;
        }

            return false;

        

    }
};