找到一個給定的字符串

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（字符串長度）的除數