---
tags: LeetCode
---

# 459. Repeated Substring Pattern
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.

Example 2:
Input: "aba"
Output: False

Example 3:
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

輸入範本如下

public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        
    }
}

##### 自行限制
禁止使用 IndexOf 方法

264 ms	33.6 MB
You are here!
Your runtime beats 25.08 % of csharp submissions.
假設沒有重複字串 , 則第二個 s 所在的位置必定是 s.Length
public bool RepeatedSubstringPattern(string s)
{
     var str = s + s;
     return str.IndexOf(s, 1) != s.Length;
}

### 直覺想法
若重複子字串的長度為 3 , 則字串 s 由重複子字串組成 , 則其長度必定是 3 的倍數. 但因為我們不知道重複子字串的長度為何 , 因此需要從長度 1 開始嘗試.

1. 使用 StringBuilder 去將重複子字串組成原始字串長度. 若與原始字串相等 , 則回傳 true.
- 但只是想知道該重複子字串是否存在於字串內 , 並不需要真的使用 Append 去將多個重複子字串組成原始字串長度來比較 , 使用 SubString() 取出對應的位置比較也可以.

368 ms	44.3 MB
You are here!
Your runtime beats 18.15 % of csharp submissions.
public bool RepeatedSubstringPattern(string s)
{
    for (int repeatStrLen = 1; repeatStrLen < s.Length / 2 + 1; repeatStrLen++)
    {
        StringBuilder repeatStr = new StringBuilder();
        if (s.Length % repeatStrLen == 0)
        {
            for (int repeatCount = 0; repeatCount < s.Length / repeatStrLen; repeatCount++)
            {
                repeatStr.Append(s.Substring(0, repeatStrLen));
            }
            if (repeatStr.ToString() == s)
            {
                return true;
            }
        }
    }
    return false;
}

2. 使用 SubString 取出第一段重複子字串 , 並開始比較其與第二 , 三 .... 段的重複子字串是否都相等 , 若都相等 , 則回傳 true , 反之 , 若有其中一個不相等 , 回傳 false
- 但是使用 SubString 仍然必須要**取出整個子字串後**才能開始比較 , 若是第一段重複子字串與第二段重複子字串在第三個字不相等 , 其實就可以直接回傳 false , 不用繼續取出剩下的字了.

116 ms	34.5 MB
You are here!
Your runtime beats 55.78 % of csharp submissions.
public bool RepeatedSubstringPattern(string s)
{
    for (int repeatStrLen = 1; repeatStrLen < s.Length / 2 + 1; repeatStrLen++)
    {
        if (s.Length % repeatStrLen == 0 && CheckRepeatStr(s, repeatStrLen))
        {
            return true;
        }
    }
    return false;

    bool CheckRepeatStr(string str, int repeatStrLen)
    {
        var str1 = str.Substring(0, repeatStrLen);
        for (int divide = repeatStrLen; divide < str.Length; divide += repeatStrLen)
        {
            var str2 = str.Substring(divide, repeatStrLen);
            if (str1 != str2)
            {
                return false;
            }
        }
        return true;
    }
}

3. 比較第一段重複子字串與其後重複子字串是否相等 , 只不過是一個字一個字去比對.

88 ms	30.4 MB
You are here!
Your runtime beats 88.12 % of csharp submissions.
public bool RepeatedSubstringPattern(string s)
{
    for (int repeatStrLen = 1; repeatStrLen < s.Length / 2 + 1; repeatStrLen++)
    {
        if (s.Length % repeatStrLen == 0 && CheckRepeatStr(s, repeatStrLen))
        {
            return true;
        }
    }
    return false;

    bool CheckRepeatStr(string str, int repeatStrLen)
    {
        for (int divide = repeatStrLen; divide < str.Length; divide += repeatStrLen)
        {
            for (int index = 0; index < repeatStrLen; index++)
            {
                if (str[index] != str[index + divide])
                {
                    return false;
                }
            }
        }
        return true;
    }
}

4. 改寫 [28. Implement strStr()使用的 KMP 演算法](https://hackmd.io/rh1MY74YQV-oS2RDYr3DkQ?view) .
- FaileFunction 會去計算每一個字前一個的最大重疊數為多少 ,
- 以 abcabc 為例 , 第一個字預設填入 -1 , 第二個 b 前一個字是 a , 與第一個 a 重疊 , 所以為 1 , 第二個 c 前面是 ab , 與第一個 ab 重疊 , ab 是兩個字 , 所以為 2 以此類推 ...
-
| a | b | c | a | b | c |
| --- | --- | --- | --- | --- | --- |
| -1 | 0 | 0 | 0 | 1 | 2 |
- 原本的 FaileFunction 的值代表失敗時 , 應該退回的 index 位置 . 但此題 , 我需要知道最後一個字的最大重疊數為多少 , 因此將多 new 一個字的空間 (new int[str.Length + 1]) 以及迴圈控制讓其多跑一次 (index < str.Length - 1)

80 ms	33.2 MB
You are here!
Your runtime beats 95.38 % of csharp submissions.
public bool RepeatedSubstringPattern(string s)
{
     var faileNums = GetFaileFunction(s);
     int maxOverlapLen = faileNums[s.Length];
     bool isRepeat = !(maxOverlapLen * 2 < s.Length) &&   // 若是由重複子字串組成 ,　則 maxOverlapLen 至少是長度的一半
                     s.Length % (s.Length - maxOverlapLen) == 0; // .Length - maxOverlapLen 為重複子字串的長度.
     return isRepeat;

     int[] GetFaileFunction(string str)
     {
          //if (str.Length <= 1)
          //{
          //    return new int[] { -1 };
          //}

          // 初始條件
          int[] FailePositions = new int[str.Length + 1]; // new int[str.Length]
          int index = 0;
          int backTrackPosition = FailePositions[0] = -1; // 若 backTrackPosition 為 -1 則代表第一位即配對失敗

          // 填滿 FailePositions
          // backTrackPosition [index] 的值代表 str[0] ~ str[index-1] 的連續比對成功次數 
          while (index < str.Length) // (index < str.Length - 1)
          {
               if (backTrackPosition == -1 || str[index] == str[backTrackPosition])
               {
                    FailePositions[++index] = ++backTrackPosition;
               }
               else
               {
                    backTrackPosition = FailePositions[backTrackPosition];
               }
          }
          return FailePositions;
     }
}

### 參考
[[LeetCode] Repeated Substring Pattern 重复子字符串模式](https://www.cnblogs.com/grandyang/p/6087347.html)

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: