在给定的字符串中查找重复的子字符串模式

Question

给定一个非空字符串，检查它是否可以通过取它的子串并将多个该子串附加在一起构造出来。你可以假设给定的字符串仅包含小写英文字母，并且其长度不超过10000。

例如1： 输入："abab" 输出：True 说明：它是子串"ab"两次。

例如2： 输入："aba" 输出：False 例如3： 输入："abcabcabcabc" 输出：True 说明：它是子串"abc"四次。（子串"abcabc"两次）

我在一个在线编程网站上找到了上述问题，网址在这里。我提交了下面的答案，在自定义测试用例中可以运行，但在提交时会出现超时异常。我尝试了其他正则表达式模式匹配的方法，但是预期会需要更多时间，并且也会失败。

public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int substringEndIndex = -1;
        int i = 0;
        char startOfString = str.charAt(0);
        i++;
        char ch;
        while(i < str.length()){
            if((ch=str.charAt(i)) != startOfString){
                //create a substring until the char at start of string is encountered 
                i++;
            }else{
                if(str.split(str.substring(0,i)).length == 0){
                    return true;
                }else{
                    //false alarm. continue matching.
                    i++;
                }
            }
        }
        return false;
    }
}

有没有想法，我花费了太多时间在哪里。

- user1242321

---

请查看此内容：(.+?)\1 在Regex101上的演示：https://regex101.com/r/AiPdzC/3 - Mohammad Yusuf

@MYGz 无法与 abcabcabc 兼容。 - James

Answer 1

这个问题有一个一行代码的解决方案。将给定字符串重复两次并删除新创建字符串的第一个和最后一个字符，检查给定字符串是否为新创建字符串的子串。

def repeatedSubstringPattern(self, s: str) -> bool:
     return s in (s + s )[1: -1]

例如:

1. 字符串： abab。 重复字符串：abababab。 移除首尾字符：bababa。 检查abab是否为bababa的子字符串。
2. 字符串：aba。 重复字符串：abaaba。 移除首尾字符：baab。 检查aba是否为baab的子字符串。

数学证明：

令P为在字符串S中重复K次的模式。

S = P*K。

通过重复字符串S创建新字符串N

N = S+S。

令F为字符串N的第一个字符，L为字符串N的最后一个字符

N = ( F+ P*(K-1) )+ (P*(K-1) + L)

N = F+ P(2K-2)+ L

如果K = 1. 即只重复一次字符串

N = F+L. //因为N != S 所以False

如果K ≥ 2.

N = F+k'+ N

其中k'≥K。由于我们有S=P*K。 所以，S必须在N中。

我们可以进一步使用KMP算法来检查S是否为N的子字符串。这将给出O(n)的时间复杂度。

- Manish Chauhan

Answer 2

你可以使用Z算法

给定长度为n的字符串S，Z算法生成一个数组Z，其中Z[i]是从S[i]开始的最长子串的长度，该子串也是S的前缀，即最大的k使得对于所有0≤j

为您的字符串构建Z数组，并查找是否存在这样的位置i，使得i+Z[i]=n且i是n（字符串长度）的除数。

- MBo

Answer 3

一个简短而易于理解的逻辑是：

def repeatedSubstringPattern(s: str):
    for i in range(1,int(len(s)/2)+1):
        if set(s.split(s[0:i])) == {''}:
            return True 
    return False

你也可以写 return i 来返回重复模式后面的数字。

- Shikhar Johri

---

这可能对所有人来说并不是显而易见的。当 set(s.split(s[0:i])) == {''} 返回 true 时，是什么情况？ - ryanwebjackson