找到一个给定的字符串

Question

给定一个非空字符串检查在重复的子字符串模式，如果它可以通过取它的一个子串并追加子的多个副本，一起构成。你可以假设给定的字符串只包含小写英文字母和它的长度不会超过10000

例1： 输入：“ABAB”

输出：真

说明：这是串“ ab“两次。 实施例2： 输入： “ABA”

输出：假 实施例3： 输入： “abcabcabcabc”

输出：真

说明：这是子串 “ABC” 的四倍。 （和子“ABCABC”两次。）

我发现一个在线编程网站here上述问题。我提交了以下适用于自定义测试用例的答案，但在提交时获得的时间超过了例外。我尝试了其他正则表达式模式匹配的方式，但正如预期的那样，这应该比这种方式花费更多的时间，并且也会失败。

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

可以使用Z-algorithm

给定长度n的串S，则Z算法产生一个阵Z 其中Z [i]为所述最长子串的从S [I] 开始其长度也是S的前缀，即最大K，使得 S [j]的= S [I + J]对于所有0≤Ĵ<ķ。请注意，Z [i] = 0意味着 S [0]≠S [i]。为了更容易的术语，我们将把子这 也是一个前缀作为前缀字符串。

构建Z-阵列为您的字符串，找到这样的位置i是否存在该i+ Z[i] = n和我为n（字符串长度）的除数