串string:字符組成的有限序列。
一組地址連續(xù)的儲存單元，儲存字符序，可在執(zhí)行過程中動態(tài)分配，如堆。
s = "a1a2...an": 相鄰的字符有前驅(qū)和后繼關(guān)系。

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

大小比較：對組成串的字符串的編碼進行比較（ASCII）。

• ASCII: 7位二進制（128）——> 8位二進制（256）
• Unicode: 16位二進制（前256位與ASCII一樣）

串的主要功能： 查找子串位置、得到指定子串、替換指定子串等。
鏈式儲存：數(shù)據(jù)域存一個字符浪費（可存多個字符——根據(jù)需要），但不如順序結(jié)構(gòu)好用。

樸素的模式匹配算法

樸素的模式匹配算

主串長度為n，子串長度為m，則時間復(fù)雜度最壞式 O((n-m+1)m)~ O(nm)。

KMP模式匹配算法

• 優(yōu)點：不用將主串中已經(jīng)匹配過的字符進行回溯——主串的下標i值不可以變小，僅變化模式串的下標j。
• 時間復(fù)雜度O(n+m)。

next[ j ]

☆下標從1開始，根據(jù)模式串計算得 next[ j ]

j下標從1開始： next[j]數(shù)組：代表j指針之前，字符串的真前綴和真后綴的最大匹配長度k + 1。
★j下標從0開始： next[j]數(shù)組：代表j指針之前，字符串的真前綴和真后綴的最大匹配長度k。

• next[j] = k;：當模式串的第j位與主串的第i位失配時，這時主串的位置不回溯，將模式串退到第k位，再次與主串的第i位進行匹配。直到匹配成功或超出字符數(shù)量為止。

代碼層面理解：☆ j下標從0開始

參考文章：（原創(chuàng)）詳解KMP算法,

• 該文章中T為主串，P為模式串。本人代碼部分p為主串，t為模式串。

思想：利用已經(jīng)部分匹配這個有效信息，保持i指針不回溯，通過修改j指針，讓模式串盡量地移動到有效位置。
★: next[j]的值（也就是k）表示，當T[j] != P[i]時，j指針的下一步移動位置。

當匹配失敗時,j要移動到下一個位置k。存在這樣的性質(zhì)：最前面的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;
}