延期复工在家无聊,刷了几道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;
    }
};

但上述算法存在主要的性能问题是:
kmp
假如比较到最后,D和空格不等,此时一般暴力破解的方法是将ABCDABD再从上面的字符串中B位置开始比较,如下图所示:

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