Easy问题也值得用KMP？也许这就是算法之道！
Easy问题也值得用KMP？也许这就是算法之道！
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是梁唐。
非常悲催，今天这篇稿子是现写的。之前写好的稿子丢了，于是就又写了一遍……
在上一篇文章当中我们一起学习了KMP算法，我个人是挺喜欢KMP算法的。代码量不大，思维非常巧妙，最关键的是使用场景非常明确，就是两个字符串匹配。这种使用场景越明确的算法或者数据结构指向性越强，在做题的时候越容易联想到。越灵活的算法适用面越广，在做题的是时候越难想起来。
好了，我们废话就聊到这里，下面来看一道简单的例子来练练手。
这题是LeetCode第459题，难度是Easy。
重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
分析
如果是在周赛当中遇到本题，肯定都不带由于的，直接上手暴力。
首先，字符串的长度是
，意味着常数比较小的
算法都有通过的可能。而本题暴力的思路也是比较明确的，我们要判断字符串能否通过某个子串重复拷贝构成。那我们只需要枚举所有可能组成s的子串进行验证即可。
很容易想到，如果存在这样的子串，那么子串的长度一定是s长度的因数。对于一个确定的数
而言，它因数的个数是非常有限的。一个比较宽松的上限是
。极端情况下，假设1到
都可以整除
，那么此时
的因数个数就是
。这只是一个宽松的上限，如果大家精通奥数的话，还可以找到更小的上限。
每一次验证都需要遍历字符串s，那么总的复杂度就是
，在本题的规模下完全是可行的。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.length();
for (int i = n/2; i > 0; i--) {
// 如果不能整除，直接跳过
if (n % i) continue;
bool flag = true;
for (int j = i; j < n; j++) {
if (s[j] != s[j-i]) {
flag = false;
break;
}
}
if (flag) return true;
}
return false;
}
};
小试KMP
老实讲拿到这道题能想到KMP的绝对都是大拿，除了暴力解法比较容易想到之外，也的确不太容易往KMP上联想。而这正是我觉得这道题非常有价值的地方所在。
因为这涉及到KMP算法能够运行的核心原理——后缀与前缀匹配，在执行两个字符串匹配的过程当中，如果s和t当前位置不能匹配。KMP算法并不会直接放弃寻找下一个位置，而是会在t中寻找一个最大前缀，使得这个前缀能够和s的后缀构成匹配。
从这个角度出发，我们思考一下，如果某个字符串能够通过重复一个子串构成。那么将它与自身的前缀进行匹配，能够得到的最大前缀是什么？我们来看一个实际的例子：s=abcabcabcabc，s的后缀与s的前缀能够匹配的最长串（不包括s本身）是abcabcabc，刚好少了一个abc子串。那么我们用s的长度减去这个匹配的长度，就得到了子串的长度。
而求字符串后缀与前缀的方法KMP当中已经讲得很清楚了，我们只需要调用一下计算next数组的逻辑即可。如果成立，那么计算出的子串的长度需要能整除s串的长度，我们由此判断即可。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
s = '$' + s;
int n = s.length();
int next[n+2];
memset(next, 0, sizeof next);
int j = 0;
// KMP中求next数组的逻辑
for (int i = 2; i < n; i++) {
j = next[i-1];
while (j > 0 && s[j+1] != s[i]) {
j = next[j];
}
if (s[j+1] == s[i]) j++;
next[i] = j;
}
int c = n - 1 - next[n-1];
if (next[n-1] == 0) return false;
return (n-1) % c == 0;
}
};
可能有些同学会说，暴力解法不是一样能通过么，为什么还非要试一下用KMP来解决？
原因很简单，也正是我写这篇文章的初衷——我们刷题、练习的目的并不是通过，获得一个AC，而是为了实实在在地提升我们的实力，让我们有能力应付各种需要用到算法的时刻。
所以与其追求通过，不如换一种游戏的心态，追求思考分析求解的乐趣。比如说这一题，如果不是看到了大佬的书籍，我可能只会将它当做是平常的Easy问题一眼扫过，根本不会往KMP上联系，也就想不到KMP还有这种用法。日后可能遇到其他类似的问题时，还是一样束手无措。
题目是否通过，算法正不正确都不重要，重要的是我们从这一过程当中学到的东西。
与君共勉，祝大家学习愉快。