【LeetCode 459】 Repeated Substring Pattern，leetcoderepeated

【LeetCode 459】 Repeated Substring Pattern，leetcoderepeated

/*********************************
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.)
****************************/
/*********************************
思路：
   1.判断字符串长度，奇数个，则直接返回
   2.依次假设子串长度分别为1.2.3.4...size/2，暴力求解
   3.在循环中用string.substr()取子字符串依次比较，一旦出现不相等情况，则直接返回
时间复杂度
   虽然程序实现是两层嵌套循环，但在比较过程中，其实内层循环经过很少次比较久可以返回，其时间复杂度并不高。
 
 
**********************************/
bool repeatedSubstringPattern(string s) {
	int  size = s.size();
 
	if (size < 1 && size % 2 == 1)
		return false;
 
	for (int ii = 1; ii <= size/2; ++ii)
	{
		string substring = s.substr(0, ii);//依次取子串长度1.2.3...
		bool  flag = false;
		for (int jj = ii; jj < size; jj+=ii)//依次向后比较，一旦不相等，则直接返回
		{
			if (s.substr(jj, ii).compare(substring) != 0)
			{
				flag = true;
				break;
			}
		}
		if (!flag)
		{
			return  true;
		}
 
	}
	return false;
 
}