LeetCode #459：Repeated Substring Pattern(重复的子字符串)

题目描述

本题依然是使用 KMP 算法中 next 数组（最长相等前后缀）来解决。设字符串长度为 n，根据 next 数组的定义，next[i] 记录的是字符串 s[0…n-1] 的子串 s[0…i] 最长相同前后缀的长度。根据这个定义，字符串 s 的最长相等前后缀的长度为 next[n – 1]。

若 n % (n – (next[n – 1])) == 0，则说明 “数组长度 – 最长相等前后缀的长度” 正好可以被数组长度 n 整除，说明有该字符串有重复的子字符串。“数组长度 – 最长相等前后缀的长度” 相当于是第一个循环周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next(n);
        initNext(next, s);
        if (next[n - 1] != 0 && n % (n - (next[n - 1] )) == 0) { // 核心判断逻辑
            return true;
        }
        return false;
    }

    // 生成next数组
    void initNext(vector<int>& next, string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < next.size(); i ++) {
            while(j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }

            if(s[i] == s[j])
                j ++;
            
            next[i] = j;
        }
    }
};