重复的子字符串
力扣题号459
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba"
输出: false
示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
|
一道标准的KMP的题目，前缀表构成的next数组记录的就是最长相等前后缀的长度，如果next[len] != 初始化说明字符创有相同的前后缀，最长相等前后缀的长度为next[len-1] ，数组长度为len。
如果len % (len - (next[len-1])) == 0 说明正好可以被数组的长度整除(数组长度 - 最长相等前后缀的长度)，说明该字符可以由子串重复多次构成
具体的证明这里不多赘述
前缀表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.length() == 0){
return false;
}
int[] next = new int[s.length()];
hasNext(next, s);
if (next[s.length() -1] !=0 && s.length() % (s.length() - next[s.length() -1]) == 0){
return true;
}
return false;
}
private void hasNext(int [] next, String s){
int j = 0;
next[0] = j;
for (int i = 1; i < s.length(); i++) {
while (j > 0 && s.charAt(i) != s.charAt(j)){
j = next[j -1];
}
if (s.charAt(i) == s.charAt(j)){
j++;
}
next[i] = j;
}
}
}
|
