延期复工在家无聊，刷了几道leetcode的题，目前进度111 / 1340，很多题目虽能折腾折腾AC，但运行速度和内存占用往往很难达到top 10%。以leetcodeimplement strstr为例，要实现子串查找最简单的就是暴力求解，两层for循环搞起来。当然两层for循环的基础上还能有小的优化。

class Solution {
public:
    int strStr(string haystack, string needle) {
        
        int hsize = haystack.size();
        int nsize = needle.size();
        
        for(int i = 0; i <= hsize - nsize;i++)
        {
            int j = 0;
            for(j = 0;j < nsize;j++)
            {
                if(haystack[i + j] != needle[j])
                    break;
            }
            
            if(j == nsize)
                return i;
        }
        
        return -1;
    }
};

但上述算法存在主要的性能问题是：

假如比较到最后，D和空格不等，此时一般暴力破解的方法是将ABCDABD再从上面的字符串中B位置开始比较，如下图所示：

一个基本事实是，当空格与D不匹配时，可以利用已知信息，加速查询，这个例子中我们可以把搜索比较位置移动4个位置到空格前面的AB继续比较。这就是将要介绍的KMP算法的核心思想。
字符串匹配KMP算法
kmp
leetcode-kmp