代码随想录 Leetcode459. 重复的子字符串（KMP算法）

题目：

---

代码（首刷看解析 KMP算法 2024年1月18日）：

class Solution {
public:
    void getNext(string& s,vector&am服务器托管网p; next) {
        int j = 0;
        next[0] = j;
        for (int i = 1; i  0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) ++j;
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        if(n  next(n);
        getNext(s,next);
        
        int a = next[n-1];
        if(a == 0) return false;
        if(n服务器托管网 % (n - a) == 0 ){
            return true;
        }else{
            return false;
        }
    }
};

此解法读者需要了解什么是KMP算法以及KMP算法中next数组的具体含义才能理解

因为在KMP算法的next数组中，next[index]表示 index之前的最大长度的相同前缀后缀值，那么要判断整个字符串中是否由重复字串构成，只需要以下两个条件：

1.next[n – 1] ！= 0 （如果等于0，说明没有重复字串）

2.设 a = next[n – 1],如果子字符串next[a]到next[n-1]是字符串的重复最大子字符串，即 n 对这个子字符串长度可以整除

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net