当前位置： 面试刷题>> 重复的子串模式 (经典算法题500道)
### 完整题目描述
**题目：重复的子串模式**
给定一个字符串 `s`，判断字符串 `s` 是否由至少两个完全相同的子串连接而成。例如，字符串 `"aabcaabc"` 可以由 `"aabc"` 重复两次得到，因此返回 `true`。而 `"abcabcabc"` 虽然是重复的，但它由三个 `"abc"` 构成，不是由至少两个相同的子串重复而成（题目要求至少两个相同且完整的子串重复），所以按照此题目的严格定义，它应返回 `false`。
### 示例
- 输入: `"aabcaabc"`
- 输出: `true`
- 输入: `"abcabcabc"`
- 输出: `false`
- 输入: `"ababab"`
- 输出: `true`
### 解题思路
一个高效的方法是使用 KMP 算法（Knuth-Morris-Pratt 算法）的变种来寻找字符串中的最长相同前缀和后缀，但这对于面试来说可能过于复杂。一个更简单直观的方法是使用字符串拼接和比较。具体地，我们可以尝试将字符串 `s` 与它自身拼接后的字符串 `s+s` 进行比较（去掉首尾的重复部分），看是否存在一个长度等于原字符串长度一半的子串，使得这个子串与原字符串相同。
### PHP 示例代码
```php
function repeatedSubstringPattern($s) {
$len = strlen($s);
$concat = $s . $s;
// 去掉首尾相同的部分
$trimmedConcat = substr($concat, 1, $len * 2 - 2);
return strpos($trimmedConcat, $s) !== false;
}
// 测试
echo repeatedSubstringPattern("aabcaabc") ? "true" : "false"; // 输出 true
echo "\n";
echo repeatedSubstringPattern("abcabcabc") ? "true" : "false"; // 输出 false
echo "\n";
echo repeatedSubstringPattern("ababab") ? "true" : "false"; // 输出 true
```
### Python 示例代码
```python
def repeatedSubstringPattern(s):
return (s + s).find(s, 1, len(s) * 2 - 1) != -1
# 测试
print(repeatedSubstringPattern("aabcaabc")) # 输出 True
print(repeatedSubstringPattern("abcabcabc")) # 输出 False
print(repeatedSubstringPattern("ababab")) # 输出 True
```
### JavaScript 示例代码
```javascript
function repeatedSubstringPattern(s) {
const concat = s + s;
// 去掉首尾相同的部分，因为JavaScript的substring不包括结束索引
const trimmedConcat = concat.substring(1, concat.length - 1);
return trimmedConcat.includes(s);
}
// 测试
console.log(repeatedSubstringPattern("aabcaabc")); // 输出 true
console.log(repeatedSubstringPattern("abcabcabc")); // 输出 false
console.log(repeatedSubstringPattern("ababab")); // 输出 true
```
**码小课**网站中有更多关于算法和数据结构的相关内容分享，欢迎大家学习交流！