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还有这种用法。日后可能遇到其他类似的问题时，还是一样束手无措。

题目是否通过，算法正不正确都不重要，重要的是我们从这一过程当中学到的东西。

与君共勉，祝大家学习愉快。