题目

459 重复的子字符串
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成

思路

KMP算法

KMP是解决子串匹配问题的法宝，本题是在字符串内部寻找子串，也是子串匹配问题，也适用KMP。
对于重复子串问题，KMP前缀表有如下规则：

  • 如果**next[len - 1] != 0**，则说明字符串有最长相同的前后缀
  • 如果**len % (len - next[len - 1]) == 0**，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串

所以该问题只要得到前缀表再判断一下就可以了

  1. class Solution
  2. {
  3. public:
  4.     bool repeatedSubstringPattern(string s)
  5.     {
  6.         if (s.size() == 0)
  7.         {
  8.             return false;
  9.         }
  10.         int next[s.size()];
  11.         getNext(next, s);
  13.         int len = s.size();
  14.         if (next[len - 1] != 0 && len % (len - (next[len - 1])) == 0)
  15.         {
  16.             return true;
  17.         }
  18.         return false;
  19.     }
  21. private:
  22.     //获取原始前缀表
  23.     void getNext(int *next, const string &s)
  24.     {
  25.         int j = 0; // j指向前缀起始位置
  26.         next[0] = 0;
  27.         // i指向后缀起始位置,i从1开始
  28.         for (int i = 1; i < s.size(); i++)
  29.         {
  30.             while (j > 0 && s[i] != s[j])
  31.             {
  32.                 //前后缀不相同的情况
  33.                 j = next[j - 1]; // 向前回退,找j+1前一个元素在next数组里的值
  34.             }
  35.             if (s[i] == s[j])
  36.             {
  37.                 //前后缀相同的情况
  38.                 j++; // i和j向后移动,i++在for里面
  39.             }
  40.             next[i] = j;
  41.         }
  42.     }
  43. };

找规律的简便方法

KMP展现的是数学证明上的结论，本题也能从表象上展示出来：
image.png
如图，我们把两个字符串s拼接起来，如果能找到一个和s一样的子串（该子串与字符串s一样，且起始index不为0），则字符串s就是由某个字串多次重复形成的。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};