KMP算法

KMP算法

KMP算法 是一个办理模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法。
重点是找到字符串的最长公共前后缀。用最长公共前后缀在匹配的同时，实现快速跳转。
KMP的时间复杂度

假设 m为模式串strM的长度，n为待匹配的字符串strN的长度。
时间复杂度为 \(O(m+n)\)
参考文档：
KMP时间复杂度分析
[code]#includeusing namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;const int Maxn = 1e6 + 5;int la, lb;int nxt[Maxn];char a[Maxn], b[Maxn];inline void kmp() { //字符串: 1 ~ lb;        nxt[1] = 0;        for (int i = 2, j = 0; i