串

串string:字符组成的有限序列。
一组地址连续的储存单元，储存字符序，可在执行过程中动态分配，如堆。
s = "a1a2...an": 相邻的字符有前驱和后继关系。

• 空格串：" "
• 子串：
• 主串：

大小比较：对组成串的字符串的编码进行比较（ASCII）。

• ASCII: 7位二进制（128）——> 8位二进制（256）
• Unicode: 16位二进制（前256位与ASCII一样）

串的主要功能： 查找子串位置、得到指定子串、替换指定子串等。
链式储存：数据域存一个字符浪费（可存多个字符——根据需要），但不如顺序结构好用。

朴素的模式匹配算法

朴素的模式匹配算

主串长度为n，子串长度为m，则时间复杂度最坏式 O((n-m+1)m)~ O(nm)。

KMP模式匹配算法

• 优点：不用将主串中已经匹配过的字符进行回溯——主串的下标i值不可以变小，仅变化模式串的下标j。
• 时间复杂度O(n+m)。

next[ j ] ☆下标从1开始，根据模式串计算得 next[ j ]

j下标从1开始： next[j]数组：代表j指针之前，字符串的真前缀和真后缀的最大匹配长度k + 1。
★j下标从0开始： next[j]数组：代表j指针之前，字符串的真前缀和真后缀的最大匹配长度k。

• next[j] = k;：当模式串的第j位与主串的第i位失配时，这时主串的位置不回溯，将模式串退到第k位，再次与主串的第i位进行匹配。直到匹配成功或超出字符数量为止。

代码层面理解：☆ j下标从0开始

参考文章：（原创）详解KMP算法,

• 该文章中T为主串，P为模式串。本人代码部分p为主串，t为模式串。

思想：利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效位置。
★: next[j]的值（也就是k）表示，当T[j] != P[i]时，j指针的下一步移动位置。

当匹配失败时,j要移动到下一个位置k。存在这样的性质：最前面的k个字符（真前缀）和j之前的最后k个字符（真后缀）是一样的，即模式串P[0~k-1] == P[j-k ~ j-1]。

void get_next(int next[], string t)
{
    int j = 0, k = -1;
    next[0] = -1; //步骤1
    while (j < t.size() - 1)
    {
        if (k == -1 || t[j] == t[k])
        {
            next[++j] = ++k; //步骤2
        }
        else
            k = next[k]; //步骤3
    }
}

步骤1:next[0]=-1

j=0位，不匹配

步骤2:P[k] == P[j],有next[j+1] = next[j]+1 = k+1

P[k] == P[j]

步骤2改进：

P[j] == P[next[j]]

步骤3:P[k] != P[j]，k=next[k];

P[k] != P[j]，k回溯到next[k]

//kmp算法
int kmp(string p, string t)
{
    int i = 0;//主串位置
    int j = 0;//模式串位置
    int *next = new int[t.size()];
    get_next(next, t);
    while ( i < p.size() && j < t.size() ) {
        if (j == -1 || p[i] == t[j]) //主串p[i]与模式串t[j]位比较，若相等，同时往后移一位。
        {
            ++i; ++j;
        }
        else
                      //i=i-j+1； // i无需回溯
            j = next[j]; //j回溯到指定位置，
    }
    delete[] next;
    if (j == t.size()) //匹配成功
        return (i - j);
    else
        return -1;
}