[LeetCode]Repeated Substring Pattern

暴力的解法就是check每个substring看能不能重构s。优化就是对s的长度分解质因数，然后只check长度为因数的substring，时间复杂度可以优化到O(n * sqrt(n))。但是我们还有一种求最长公共前后缀的方法，如果s其有repeat substring，那么其一定存在最长公共前后缀p(p.length < s.length)使得，s.length % (s.length - p.length) == 0。例如，ababab，最长公共前后缀为abab，其满足条件，事实上s.length - p.length就是repeat substring的长度。对于abababa，其最长公共前后缀为aba，则不满足此条件。KMP求next数组就是求最长公共前后缀的方法，具体可以参考这篇文章。时间复杂度O(n)，代码如下：

	class Solution {
	public:
	bool repeatedSubstringPattern(string s) {
	int len = s.size();
	if(!len)return true;
	vector<int> next(len + 1, -1);
	int i = 0, k = -1;
	while(i < len)
	{
	if(k == -1 || s[i] == s[k])
	next[++i] = ++k;
	else
	k = next[k];
	}
	return next[len] > 0 && len % (len - next[len]) == 0;
	}
	};

view raw Repeated Substring Pattern.cpp hosted with ❤ by GitHub