题目链接

题目描述

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

示例

示例1：

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

思路

思路1：暴力匹配

思路2：字符串匹配

我们可以证明如下结论（证明过程暂时省略）

长度为 n 的字符串 s 是字符串 t = s + s 的子串，并且 s 在 tt 中的起始位置不为 0 或 n，当且仅当 s 满足题目的要求。

由此，我们可以从位置 1 来查找 t 中是否有子串 s 。

思路3：KMP算法

next 数组表示最长相等前后缀的长度，设 s 的长度为 len 则，该字符串的最长相等前后缀的长度为 next[len - 1] + 1 。
len - (next[len - 1] + 1) 其实表示了重复周期的第一周期，（写出一个符合题意的字符串的 next 数组就能清楚地看到此结论）。

题解

思路2：字符串匹配

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

思路3：KMP算法

  1. class Solution {
  2.    private:
  3.     void getNext(int* next, const string& t) {
  4.         next[0] = -1;
  5.         int j = -1;
  6.         for (int i = 1; i < (int)t.size(); ++i) {
  7.             while (j >= 0 && t[i] != t[j + 1]) {
  8.                 j = next[j];
  9.             }
  10.             if (t[i] == t[j + 1]) {
  11.                 ++j;
  12.             }
  13.             next[i] = j;
  14.         }
  15.     }
  17.    public:
  18.     bool repeatedSubstringPattern(string s) {
  19.         int len = s.size();
  20.         if (0 == len) {
  21.             return false;
  22.         }
  23.         int* next = new int[len];
  24.         getNext(next, s);
  25.         if (next[len - 1] != -1 && 0 == len % (len - (next[len - 1] + 1))) {
  26.             return true;
  27.         }
  28.         return false;
  29.     }
  30. };

复杂度分析

思路3：KMP算法

  • 时间复杂度：0459-重复的子字符串 - 图1
  • 空间复杂度：0459-重复的子字符串 - 图2