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

题目：

---

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

class Solution {
public:void getNext(string& s,vector<int>& next) {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]) ++j;next[i] = j;}}bool repeatedSubstringPattern(string s) {int n = s.size();if(n <= 1) return false;vector<int> 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 对这个子字符串长度可以整除