题目描述

代码解决

class Solution 
{
public:
    // 计算字符串s的next数组，用于KMP算法
    void getNext(int *next, const string& s)
    {
        int j = 0; // j是前缀的长度
        next[0] = 0; // 初始化next数组，第一个字符的next值为0

        for (int i = 1; i < s.size(); i++) // 注意这里的i从1开始
        {
            // 如果s[i] != s[j]，则向前回溯，直到找到匹配的前缀或到达字符串开始
            while (j > 0 && s[i] != s[j])
            {
                j = next[j - 1];
            }
            // 如果s[i] == s[j]，前缀长度增加1
            if (s[i] == s[j])
            {
                j++;
            }
            next[i] = j; // 更新next数组
        }
    }

    bool repeatedSubstringPattern(string s) 
    {
        if (s.size() == 0)
        {
            return false;
        }
        int next[s.size()];
        getNext(next, s); // 计算next数组
        int len = s.size();
        int pattern_length = len - next[len - 1]; // 计算模式字符串的长度

        // 如果next[len - 1] != 0 且 len 能被 pattern_length 整除，则表示有重复的模式
        if (next[len - 1] != 0 && len % pattern_length == 0) 
        {
            return true;
        }
        return false;
    }
};

1. 计算Next数组：

   • getNext 函数通过计算 next 数组来确定每个字符前缀的最大长度，使得这些前缀同时也是后缀。
   • 具体地，对于每一个字符 s[i]，如果它不能匹配当前的前缀字符 s[j]，则通过 j = next[j - 1] 回溯到前一个匹配位置，直到找到匹配的前缀或到达字符串的开始。

2. 检查重复子串模式：

   • 如果 next[len - 1] 不为0，表示字符串存在部分重复。
   • 计算模式字符串的长度 pattern_length，这个长度等于字符串的总长度减去最后一个前缀值 next[len - 1]。
   • 如果字符串长度 len 可以被 pattern_length 整除，则表示字符串可以由重复的模式字符串构成。