Rearch Interest: Visualization">
459. 重复的子字符串
题目描述
给定一个非空的字符串 s
，检查是否可以通过由它的一个子串重复多次构成。
示例 1: >输入: "abab" >输出: True
>解释: 可由子字符串 "ab" 重复两次构成。
示例 2: >输入: "aba" >输出: False
示例 3: >输入: "abcabcabcabc" >输出:
True >解释: 可由子字符串 "abc" 重复四次构成。
(或者子字符串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 104s由小写英文字母组成
我的代码 (Timeout)
{.line-numbers} 1
2
3
4
5
6
7
8
9
10
11
12
class MySolution459
{
public boolean repeatedSubstringPattern(String s)
{
if (s==null||s.length()<=1) return true;
for (int i=0; i<s.length(); i++)
if (s.split(s.substring(0,i)).length==0)
return true;
return false;
}
}
1 | class MySolution459 |
方法一: 枚举
\(T(N) = O(N^2)\), \(S(N) = O(1)\)
如果一个长度为 \(n\) 的字符串 \(s\) 可以由它的一个长度为 \(n'\) 的子串 \(s'\) 重复多次构成，那么: - \(n\) 一定是 \(n'\) 的倍数； - \(s'\) 一定是 \(s\) 的前缀； - 对于任意的 \(i∈[n',n)\), 有 \(s[i]=s[i-n']\)
即: \(s\) 中长度为 \(n'\) 的前缀就是 \(s'\) ，并且在这之后的每一个位置上的字符 \(s[i]\) ，都需要与其之前的第 \(n'\) 个字符 \(s[i-n']\) 相同。
因此，我们可以从小到大枚举 \(n'\) ，并且字符串 \(s\) 进行遍历，进行上述的判断。 可以进行的一个小优化是，因为子串至少重复一次，因此 \(n'\) 不会大于 \(n\) 的一半，我们只需要在 \([1,\frac{n}{2}]\) 的范围内枚举 \(n'\) 即可。
代码
{.line-numbers} 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//即 从i=1开始不断假设子串的长度为i++（要成为子串的话必须n%i==0），
//然后从字符串的i位置j开始验证往后每个子串是否在重复上个子串的内容(s[j]是否等于s[j-i]).
class Solution459
{
public boolean repeatedSubstringPattern(String s)
{
int n = s.length();
for (int i = 1; i * 2 <= n; ++i)
{
if (n % i == 0)
{
boolean match = true;
for (int j = i; j < n && match; j++)
if (s.charAt(j) != s.charAt(j - i))
match = false;
if (match)
return true;
}
}
return false;
}
}
1 | //即 从i=1开始不断假设子串的长度为i++（要成为子串的话必须n%i==0）， |
方法二: 字符串匹配
我们可以把符合要求的字符串\(s\)写成\(s's'...s's'\)的形式，总计\(\frac{n}{n'}\)个\(s'\)。 但我们如何在不枚举\(n'\)的前提下，判断\(s\)是否能写成上述的形式呢？
如果我们移除字符串\(s\)的前\(n'\)个字符（也就是一个完整的\(s'\)），再将这些移除掉的字符保持原顺序添加到剩余字符串的末尾，那么得到的字符串依然是\(s\)。 由于\(1≤n'＜n\)，如果将两个\(s\)连接在一起，并且移除第一个和最后一个字符，那么得到的字符串一定包含\(s\)，即\(s\)是它的一个子串。
因此我们可以考虑这种方法： 将两个\(s\)连接在一起，并移除第一个和最后一个字符。 如果\(s\)是该字符串的子串，那么\(s\)就满足题目要求。
注意：我们证明的是如果\(s\)满足题目要求，那么\(s\)会具有这样的性质； 但我们的方法使用的却是如果\(s\)具有这样的性质，那么\(s\)就会满足题目要求。 因此，光证明充分性是不够的，我们还需要证明其必要性。 必要性的证明可见KMP思路的正确性证明部分。
实现: 我们可以从位置 \(1\) 开始查询，并且希望查询结果不为位置 \(n\)。 这与移除字符串的第一个和最后一个字符是一样的。
代码
{.line-numbers} 1
2
3
4
5
6
7
class Solution459
{
public boolean repeatedSubstringPattern(String s)
{
return (s + s).indexOf(s, 1) != s.length();
}
}
1 | class Solution459 |
方法三: KMP算法
上一个方法中我们使用了内置的字符串查找函数，而这个函数可以用KMP算法实现。
需要注意以下几点: - KMP算法虽然具有良好的理论时间复杂度上限，但是大部分语言内置的字符串查找函数并不是用KMP算法实现的。 这是因为在实现API时，我们需要在平均时间复杂度和最坏时间复杂度两者之间进行权衡。 普通的暴力匹配算法，以及优化过的BM算法，都拥有比KMP算法更加优秀的平均时间复杂度。 - 学习KMP算法时，一定要理解其本质。 如果放弃阅读晦涩难懂的材料而直接去阅读代码，是永远无法学会KMP算法的。甚至很难理解KMP算法中的任意一行。
由于本体就是在一个字符串中查找另一个字符串是否出现，因此可以直接套用KMP算法。
这里不再对KMP算法进行赘述。 以下留下三个思考题，以检验学习成果: -
假设查询串的长度为\(n\)，模式串的长度为\(m\)，我们需要判断模式串是否为查询串的子串。
使用KMP算法处理该问题时的时间复杂度是多少？在分析时间复杂度时使用了哪一种方法？
- 如果有多个查询串，平均长度为\(n\)，数量为\(k\)，那么总的时间复杂度是多少？ -
在KMP算法中，对于模式串，我们需要预处理出一个fail数组（有时也称为next数组、π数组等）。这个数组到底代表了什么？
代码
1 | class Solution459 |