# C#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.

Input: “abab”

Output: True

Explanation: It’s the substring “ab” twice.

Input: “aba”

Output: False

Input: “abcabcabcabc”

Output: True

Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)

```public class Program {

public static void Main(string[] args) {
var s = "Iori's Blog";

var res = RepeatedSubstringPattern(s);
Console.WriteLine(res);

s = "abaababaab";

res = RepeatedSubstringPattern2(s);
Console.WriteLine(res);

}

private static bool RepeatedSubstringPattern(string s) {
//LeetCode 超出内存限制，未AC
//基本思路是一个指针截断字符串
//指针前所有的字符串为子字符串参考计算
//往后循环看每一段是否相同
//如果每一段都相同，则满足题意
for(var i = 0; i < s.Length / 2; i++) {
var sub = s.Substring(0, i + 1);
if(s.Length % sub.Length != 0) continue;
var nums = s.Length / sub.Length;
for(var j = 1; j < nums; j++) {
if(s.Substring(j * sub.Length, sub.Length) != sub) break;
if(j == nums - 1) return true;
}
}
return false;
}

private static bool RepeatedSubstringPattern2(string s) {
//基本思路是一个指针截断字符串
//指针前所有的字符串为子字符串参考计算
//以此字符串循环构建新字符
//比较新构建的字符串是否和原串相同
//变量 repeat 不能使用字符串，否则效率较低
//LeetCode 会TLE超时无法AC
var length = s.Length;
for(var i = length / 2; i >= 1; i--) {
if(length % i == 0) {
var repeat = new StringBuilder();
for(var j = 0; j < length / i; j++) {
repeat.Append(s.Substring(0, i));
}
if(repeat.ToString() == s) return true;
}
}
return false;
}

}```

```False
True```