想整理一下 字符串匹配 就拿这道题为例吧
注：没有讲解，只是单纯的整了个板子扔上去
注：下面顺序随机，与难度或复杂度等无关

双指针 (最暴力方法无之一)

不断向后移动p，如果和待匹配字符串开始一样就开始尝试匹配，不是就继续走

class Solution {
public:
    int strStr(string haystack, string needle) {
        int L(needle.length()), n(haystack.length());
        if(L==0) return 0;

        int p = 0;
        while(p < n-L+1){
            while(p < n-L+1 && haystack[p] != needle[0]) ++p;
            int a(0), b(0);//a记录以及匹配的长度，b记录匹配到了第几个
            while(b < L && p < n && haystack[p] == needle[b])
                ++p, ++b, ++a;
            if(a == L) return p-L;
            p = p-a+1;
        }
        return -1;
    }
};
/*
时间复杂度： O((N-L)*L) 最好为O(n)
空间复杂度: O(1)
*/

Rabin Karp (字符串哈希)

说白了就是字符串哈希一下，然后比较两个是否相等

class Solution {
public:
    int strStr(string haystack, string needle) {
        int L(needle.length()), n(haystack.length());
        if(L > n) return -1;
        int a = 26;
        long long p = 1<<31;
        long long h = 0, ref_h=0;
        for(int i = 0; i < L; ++i){
            h = (h*a + haystack[i]-'a')%p;
            ref_h = (ref_h*a+needle[i]-'a')%p;
        }
        if(h == ref_h) return 0;

        long long o = 1;
        for(int i = 1; i <= L; ++i) o = o*a % p;

        for(int l = 1; l < n-L+1; ++l){
            h = (h*a-(haystack[l-1]-'a')*o + haystack[l+L-1] - 'a')%p;
            if(h == ref_h) return l;
        }

        return -1;
    }
};
/*
时间复杂度：O(n) (计算哈希是复杂度O(L), 之后(n-L)次循环，每次循环常数复杂度
空间复杂度: O(1)
*/

KMP

经典的算法了，不知道劝退了多少人(小声BB)

class Solution {
public:
    int strStr(string haystack, string needle) {
        int L(needle.size()), n(haystack.size()); 
        // int m = haystack.size();
        //int n = needle.size();
        if(L==0) return 0;
        haystack = " "+haystack;
        needle = " "+needle;
        vector<int> ne(n+10);
        for(int i = 2,j = 0;i <= L; ++i){
            while(j && needle[i] != needle[j+1]) j = ne[j];
            if(needle[i] == needle[j+1]) ++j;
            ne[i] = j;
        }
        for(int i = 1, j = 0; i <= n; ++i){
            while( j && haystack[i] != needle[j+1]) j = ne[j];
            if(haystack[i] == needle[j+1]) j++;
            if(j == L) return i-L;
        }
        return -1;
    }
};

Horspool (后缀匹配+简化)

其实就是暴力加了点优化

class Solution {
public:
    int strStr(string haystack, string needle) {
        int L(needle.size()), n(haystack.size());
        if(L==0) return 0;
        int d[30];
        for(int i = 0; i < 30; ++i) d[i] = L;
        for(int i = 0; i < L-1; ++i) d[needle[i]-'a'] = L-i-1;


        int i = L - 1;
        while(i <= n - 1)
        {
            int k = 0;
            while(k <= L - 1 && needle[L - 1 - k] == haystack[i - k]) ++k;

            if(k == L) return i - L + 1;
            else i += d[haystack[i] - 'a'];
        }

        return -1;
    }
};
/*
时间复杂度: O(mn), 数据随机的情况下可近似看作O(n)
*/

Boyer-Moore (后缀匹配)

class Solution {
public:
    int strStr(string haystack, string needle) {
        return str_bm(&haystack[0], haystack.size(), &needle[0], needle.size());
    }
#define SIZE 256    //字符集字符数
    void generateBadChar(char *b, int m, int *badchar)//(模式串字符b，模式串长度m，模式串的哈希表)
    {
        int i, ascii;
        for(i = 0; i < SIZE; ++i)
        {
            badchar[i] = -1;//哈希表初始化为-1
        }
        for(i = 0; i < m; ++i)
        {
            ascii = int(b[i]);  //计算字符的ASCII值
            badchar[ascii] = i;//重复字符被覆盖，记录的是最后出现的该字符的位置
        }
    }
    void generateGS(char *b, int m, int *suffix, bool *prefix)//预处理模式串，填充suffix，prefix
    {
        int i, j, k;
        for(i = 0; i < m; ++i)//两个数组初始化
        {
            suffix[i] = -1;
            prefix[i] = false;
        }
        for(i = 0; i < m-1; ++i)//b[0,i]
        {
            j = i;
            k = 0;//公共后缀子串长度(模式串尾部取k个出来，分别比较)
            while(j >= 0 && b[j] == b[m-1-k])//与b[0,m-1]求公共后缀子串
            {
                --j;
                ++k;
                suffix[k] = j+1;
                //相同后缀子串长度为k时，该子串在b[0,i]中的起始下标
                // (如果有多个相同长度的子串，被赋值覆盖，存较大的)
            }
            if(j == -1)//查找到模式串的头部了
                prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串
        }
    }
    int moveByGS(int j, int m, int *suffix, bool *prefix)//传入的j是坏字符对应的模式串中的字符下标
    {
        int k = m - 1 - j;//好后缀长度
        if(suffix[k] != -1)//case1，找到跟好后缀一样的模式子串（多个的话，存的靠后的那个（子串起始下标））
            return j - suffix[k] + 1;
        for(int r = j + 2; r < m; ++r)//case2
        {
            if(prefix[m-r] == true)//m-r是好后缀的子串的长度，如果这个好后缀的子串是模式串的前缀子串
                return r;//在上面没有找到相同的好后缀下，移动r位，对齐前缀到好后缀
        }
        return m;//case3,都没有匹配的，移动m位（模式串长度）
    }
    int str_bm(char *a, int n, char *b, int m)//a表示主串，长n; b表示模式串,长m
    {
        int *badchar = new int [SIZE];//记录模式串中每个字符最后出现的位置
        generateBadChar(b,m,badchar);     //构建坏字符哈希表
        int *suffix = new int [m];
        bool *prefix = new bool [m];
        generateGS(b, m, suffix, prefix);   //预处理模式串，填充suffix，prefix
        int i = 0, j, moveLen1, moveLen2;//j表示主串与模式串匹配的第一个字符
        while(i < n-m+1)
        {
            for(j = m -1; j >= 0; --j)  //模式串从后往前匹配
            {
                if(a[i+j] != b[j])
                    break;  //坏字符对应模式串中的下标是j
            }
            if(j < 0)   //匹配成功
            {
                delete [] badchar;
                delete [] suffix;
                delete [] prefix;
                return i;   //返回主串与模式串第一个匹配的字符的位置
            }
            //这里等同于将模式串往后滑动 j-badchar[int(a[i+j])] 位
            moveLen1 = j - badchar[int(a[i+j])];//按照坏字符规则移动距离
            moveLen2 = 0;
            if(j < m-1)//如果有好后缀的话
            {
                moveLen2 = moveByGS(j,m,suffix,prefix);//按照好后缀规则移动距离
            }
            i = i + max(moveLen1,moveLen2);//取大的移动
        }
        delete [] badchar;
        delete [] suffix;
        delete [] prefix;
        return -1;
    }
};
/*
时间复杂度： 最差: O(nm) 最优:O(n/m)
还有一个优化版的：Turbo-BM 但是找不到了，记得可以让最差降到O(n)
此代码来自：
 https://blog.csdn.net/qq_21201267/article/details/92799488
*/