完整题目描述

题目：重复的子串模式

给定一个字符串 s，判断字符串 s 是否由至少两个完全相同的子串连接而成。例如，字符串 "aabcaabc" 可以由 "aabc" 重复两次得到，因此返回 true。而 "abcabcabc" 虽然是重复的，但它由三个 "abc" 构成，不是由至少两个相同的子串重复而成（题目要求至少两个相同且完整的子串重复），所以按照此题目的严格定义，它应返回 false。

示例

• 输入: "aabcaabc"

• 输出: true

• 输入: "abcabcabc"

• 输出: false

• 输入: "ababab"

• 输出: true

解题思路

一个高效的方法是使用 KMP 算法（Knuth-Morris-Pratt 算法）的变种来寻找字符串中的最长相同前缀和后缀，但这对于面试来说可能过于复杂。一个更简单直观的方法是使用字符串拼接和比较。具体地，我们可以尝试将字符串 s 与它自身拼接后的字符串 s+s 进行比较（去掉首尾的重复部分），看是否存在一个长度等于原字符串长度一半的子串，使得这个子串与原字符串相同。

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 示例代码

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 示例代码

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

码小课网站中有更多关于算法和数据结构的相关内容分享，欢迎大家学习交流！