LeetCode459 Repeated Substring Pattern

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

样例

Example 1:

1
2
3
4
5
Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.

Example 2:

1
2
3
Input: "aba"

Output: False

Example 3:

1
2
3
4
5
Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

思路

判断字符串是否存在循环节。

kmp算法找字符串循环节的一个应用,具体见KMP算法 —— next 数组的应用 —- 前缀中最小循环节,最大重复次数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int fail[10005];
void getFail(string s) {
int i = 0, j, len = s.size();
j = fail[0] = -1;
while (i < len) {
while (j != -1 && s[i] != s[j]) j = fail[j];
fail[++i] = ++j;
}
}
bool repeatedSubstringPattern(string str) {
getFail(str);
int len = str.size();
return fail[len] != 0 && len % (len - fail[len]) == 0;
}
};
分享到 评论