String

KMP

算法作用

在长串T中查找短串P，如果存在则返回短串位置，不存在则返回-1

思想

直观的暴力搜索方法即从长串第一位开始和短串进行匹配，如果无法匹配，再从长串第二位开始匹配，即每次不匹配后只把短串往后移动一位，直到短串到达末尾为止

但其实每次可以将短串多向后挪动几位，因为已经短串匹配过的位是已知的，可以判断是否会发生匹配，如下例

长串ABCABABCABD中查找短串ABCABD，第一次不匹配之后，已经知道匹配过的五位是ABCAB，可以直接把短串向后移动三位，因此之后的两位都不匹配

ABCABABCABD
ABCABD
   ABCABD

具体来说，就是针对短串P构建一个next表，next[j]表示P[j]位不匹配后，应该把P串的第next[j]位移到这里，继续进行匹配

主算法

KMP主算法流程如下，相对好理解，和暴力搜索类似，区别在于每次不匹配时可以把短串多向后移动几位

其中next表第一位以及中间一些位 (某些和第一位字符相同的位) 可能是-1，表示直接从下一位开始匹配，这也很好理解，短串第1位已经和长串的i位不匹配，已经无法再把更左的短串位拿来和长串匹配，所以就直接和长串下一位开始匹配

以下T是长串，P是短串

int match(const string& T, const string& P) {
    int* next = buildNext(P);
    int n = T.size(), i = 0;
    int m = P.size(), j = 0;
    while (j < m && i < n) {
        if (0 > j || T[i] == P[j]) {
            i ++; j ++;
        }
        else j = next[j];
    }
    delete[] next;
    if (i == n && j < m) return -1; // 如果i匹配到最后一位，成功匹配的话，j应该是m
    return i - j;
}

算法重点在于如何构建next表，next表中$N[j]=t$的含义其实是，$P[0,j)$中长度为t的真前缀，与长度为t的后缀相同，这里t取所有满足该条件的前缀/后缀中的最大长度，当某位不匹配时，把短串后移到前缀覆盖刚才的后缀

例如ABCABD，next表如下

0	1	2	3	4	5
A	B	C	A	B	D
-1	0	0	0	1	2

对N[4]来说，前面ABCA一位前缀和后缀相同，对N[5]来说即为两位

构造Next表

构建next表的方法和主流程类似，即把短串和自身进行比较

int* buildNext(const string& P) {
    size_t m = P.size(), j = 0;
    int* N = new int[m];
    int t = N[0] = -1;
    while (j < m - 1) {
        if (0 > t || P[j] == P[t]) {
            j ++; t ++;
            N[j] = t;
        }
        else t = N[t];
    }
    return N;
}

最开始将第一位置-1很显然，之后的循环可以这样理解，逐位确定N[j]，t表示用另一个短串的t长前缀和目前j前t位后缀来比较

• 如果P[j]和P[t]相同，那么已经找到最大匹配的前缀和后缀，则把j和t后移并更新N[j]
• 如果不相同，表示目前前缀过长，这时已经可以借助建立好的部分next表来进行后移，即t=N[t]，用更小的前缀来匹配后缀

这里可以改进的是，如果j和t后移后，P[t]和P[j]相等，那么这时如果P[j]无法匹配，退到t处也肯定无法匹配，所以直接退到N[t]，代码如下

这里注意已经将t和`j向前推一位，和if判断中的结果不一定一样

int* buildNext(const string& P) {
    int m = P.size();
    int* N = new int[m]();
    int t = -1, N[0] = -1, j = 0;
    while (j < m - 1) {
        if (t < 0 || P[t] == P[j]) {
            t ++; j ++;
            N[j] = (P[t] == P[j]) ? N[t] : t;
        }
        else t = N[t];
    }
    return N;
}