算法比较

对长为m的源串，长为n的子串进行匹配

算法	最坏时间复杂度	最优时间复杂度
暴力双循环	O(m*n)	\
KMP	O(m+n)	\
Sunday	O(m*n)	O(m/n)

KMP算法

核心:充分利用已知的信息，通过构建部分匹配表（Partial Match Table）来控制匹配位。

可参考以下Youtube视频：

虽然懂了KMP的大概思路，但写出来的代码还是一堆bug呀，果然还是功力不够，不过还好有Sunday算法，简单易懂，速度又快！

Sunday算法

Sunday算法是对BM算法（Boyer-Moore算法）的进一步优化，是现代文字处理器中常用的字符串匹配算法。

核心：尽可能的跳过较多的字符串

参数介绍：

主串S
模式串P
i 为主串S的的index，j为模式串P的index。
m 指着模式串最后一位与主串对应的位置的下一位（现在不理解，可以看下面的实例）。
slen：主串S的长度
plen: 模式串P的长度

算法步骤

首先初始状况是i=j=0，i指着S的首位，j指着P的首位，m则指着S的第plen+1位，及第6位
判断S[i]与P[j]是否相等。
- 若相等则i++，j++，比较下一位。
- 若相等，且j==plen-1，也就是比较完毕了，则说明找到了目标，直接返回i-j即可。
- 若是不相等，则需要看S[m]字符是否在P中出现
  - 若没出现，则直接将j指向S[m]的下一位，i指向m+1的位置，j则重新置0，m则更新为新的i+plen。
  - 若出现了，还是要想办法尽可能大的将P往后滑动。首先，找到模式串P中与S[m]字符相等字符的位置，然后将P串中的该字符与S[m]字符对齐。对齐时，P向右滑动了多少格，i更新的时候就加几，j则重置为0，m还是用更新后的i加plen：新i+plen。
  - 更新后若出现m>slen的情况，说明已经比较完毕，仍没有找到目标，则return -1。

实例讲解

参数

S: string matching algorithm
P: rithm
slen: 25
plen: 5

首先将i指向S首位，j指向P首位，即i=j=0. m则指向S的第plen位，也就是第5位。

初始化 i=0, j=0, m=5，状态如下所示

S	s	t	r	i	n	g
	i					m
P	r	i	t	h	m
	j

比较 S[0] 与 P[0]，发现不等，则直接看 S[5] 是否在P中出现，'rithm'里是没有'g'的，故直接将P移到m的下一位。

第一步更新后 i=6, j=0, m=11，状态如下所示

S		m	a	t	c	h
	i					m
P	r	i	t	h	m
	j

比较S[6]与P[0]，发现' '不等于'r'，且S[11]在'rithm'的第3位出现。则需要将P中的'h'与S中的'h'对齐，只需要将P串向右移动两格（对应于i=m-3=8）

第二步更新后 i=8, j=0, m=13，状态如下所示

S	a	t	c	h	i	n
	i					m
P	r	i	t	h	m
	j

同样S[8]!=P[0]，且S[13]为'n'不存在于'rithm'，因此直接将P滑到m的下一位

第三步更新后 i=14, j=0, m=19

S	g		a	l	g	o
	i					m
P	r	i	t	h	m
	j

再次比较, S[14]!=P[0], 且S[19]不在P中，再次将P滑到m的下一位。

第四步更新后 i=20, j=0, m=25

S	r	i	t	h	m
	i					m
P	r	i	t	h	m
	j

这时候可以看到，'rithm'是匹配上了，一步一步比较，i与j逐步加1，直至j=4时，比较完毕，得到结果i-j=24-4=20。

LeetCode 题源

LeetCode 28. Implement strStr()

AC 代码

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()){
           return 0;
        }
        int slen=haystack.length();
        int plen=needle.length();
        int i=0,j=0,k,m=plen; // i 指 haystack，j 指 needle，
        while(i<slen){
            if(haystack[i]!=needle[j]){
                for(k=plen-1;k>=0;k--){
                    if(needle[k]==haystack[m])
                        break;
                }
                i=m-k;
                j=0;
                m=i+plen;
                if(m>slen){
                    return -1;
                }
            }else{
                if(j==plen-1){
                    return i-j;
                }
                i++,j++;
            }
        }
        return -1;
        
    }
};