字符串匹配问题

假设有两个字符串P和S，我们想要知道P是否为S的子串，这就是最简单的字符串匹配问题，本文将介绍如何使用KMP算法解决这个问题。

例如：ab是cabc的，ab不是cac的子串，如果要严格定义的话，我们引入如下符号： 假设S是一个长度为n的字符串，假设S[i]表示字符串S第i个位置的字符（下标从0开始），S[i..j]表示由S[i]S[i+1]…S[j]组成的字符串，其中0<=i<=j<n；那么称S[i..j]为S的子串。 备注：后面称S为匹配串，P为模式串

蛮力算法

蛮力算法很好理解，直接上代码吧

bool isMatching(string p, string s) {
    int m = p.size(), n = s.size();
    for (int i = 0; i <= n-m; i++) {
        for (int j = 0; j < m; j++) {
            if (s[i+j] != p[j]) break;
            if (j == m - 1) return true;
        }
    }
    return false;
}

假设s的长度为n，p的长度为m，其实上面的代码就是判断是否存在大于等于0，小于等于m-n的i，满足p等于s[i]s[i+1]…s[i+m-1]。

存在的问题

假设模式串长度为m，匹配串长度为n，显然蛮力匹配时间复杂度为，如果使用kmp算法的话，时间复杂度可以优化到

理解kmp的几个步骤

个人感觉kmp算法还是蛮难理解的，第一接触完全摸不着头脑，看了很多遍才理解，这里梳理一下几个关键步骤，如果把关键步骤都理解清楚了，再梳理一遍就可以自己写出kmp算法来了。
关键步骤一：理解前缀、后缀的基本概念。
关键步骤二：理解next数组的定义。
关键步骤三：理解使用next数组优化字符串匹配过程。
关键步骤四：求解next数组。
上面几乎都是围绕next数组展开的，可以说理解了next数组，也就基本理解了kmp算法。

前缀、后缀

假设S是一个长度为n的字符串，S=S[0]S[1]…S[n-1]。

前缀

那么对,S[0]S[1]…S[i]是S的一个前缀，假设用表示字符串S所有前缀的集合，那么有

例如，令S=ababc，那么有 备注：当

后缀

对，S[n-i]S[n-(i-1)]…S[n-1]是S的一个后缀，同理，假设用表示字符串S所有后缀的集合，那么有。

例如，令S=ababc，那么有 备注：当

公共缀

这里不知道取什么名字好，就叫公共缀了好了

定义1：公共缀是指一个字符串前缀和后缀的交集，即
定义2：假设,则

定义2补充说明：其实就是定义了一个函数,它代表S的公共缀中长度最长的那个元素的长度，其中s.length表示字符串s的长度

例如:
那么

备注：如果,那么

next数组定义

先不用管next数组用来干嘛的，也不用管next数组怎么求，后面会介绍，先要了解什么是next数组。

定义：假设S为一个长度为n的字符串，代表S[0]S[1]…S[i]组成的字符串（）,N是一个长度为n的数组，其中,那么N就是next数组。
例如：S=abab

使用next数组优化字符串匹配

todo

next数组求解过程

时间复杂度

牛刀小试