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

Question

给定一个非空字符串，检查它是否可以通过获取它的子字符串并将子字符串的多个副本附加在一起来构造。您可以假设给定的字符串仅由小写英文字母组成，并且其长度不会超过 10000。

示例 1：输入：“abab”

输出：真

解释：它是子串 "ab" 两次。示例 2：输入：“aba”

输出：False 示例 3：输入：“abcabcabcabc”

输出：真

解释：它是子串 "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;
    }
}

关于我花了太多时间的任何想法。

Answer 1

有一个字面上的单行解决方案。重复给定的字符串两次并删除新创建的字符串的第一个和最后一个字符，检查给定的字符串是否是新创建的字符串的子字符串。

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

例如：

1. str：阿巴。重复 str：abababab。删除第一个和最后一个字符：bababa。检查 abab 是否是 bababa 的子串。
2. STR：阿巴。重复 str: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 所以假

如果 K ? 2.

N = F+k'+ N

哪里k'？K。因为我们的 S=P*K。所以，S 必须在 N 中。

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