第五章 串

串：由零个或多个字符组成的有限序列，又名叫字符串。

朴素模式匹配算法：

时间复杂度为 O(n+m)                  最坏情况时间复杂度： O((n-m+1)*m)

KMP模式匹配算法（时间复杂度：O(n+m))(好马不吃回头草)：

K—克努特 M—莫里斯 P—普拉特

以下是我从网上找的kmp算法讲解链接：
https://www.bilibili.com/video/BV1Ys411d7yh?from=search&seid=18429832824354750254

//构建子串next数组(改进版）
void get_nextval(String T, int *nextval)
{
    int i,j;
    i = 1;
    j = 0;
    nextval[1] = 0;
    while (i < T[0])
    {
        if (j == 0 || T[i] == T[j])
        {
            ++i;
            ++j;
            if (T[i] != T[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
} //当a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval值。
//与主串比较（返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回0）
int Index_KMP(String S, String T, int pos)
{
    int i = pos;
    int j = 1;
    int nextval[255];
    get_nextval(T, nextval);
    while (i <= S[0] && j <= T[0])
    {
        if (j == 0 || S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
            j = nextval[j];
    }
    if (j > T[0])
        return i - T[0];
    else
        return 0;
}

tips:

1.空串：零个字符的串。
2.ASCII编码：由8位二进制数表示一个字符，总共表示256个字符。
Unicode编码：由16位二进制数表示一个字符，总共表示2^16个字符。与ASCII兼容，前256个字符完全相同。
3.串的模式匹配：子串的定位操作。