一、串的定義和實(shí)現(xiàn)

所謂串其實(shí)就是字符串，該小節(jié)我們會(huì)先學(xué)習(xí)串的定義和相關(guān)基本操作。也就是要探討它的邏輯結(jié)構(gòu)和基本運(yùn)算（數(shù)據(jù)結(jié)構(gòu)三要素：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算）

1.1串的定義和基本操作

1.1.1串的定義

串，即字符串（String）是由零個(gè)或多個(gè)字符組成的有序序列。
一般記為S=‘a(chǎn)1a2…an’(n>=0)
其中，S是串名，單引號(hào)括起來(lái)的字符序列是串的值，ai可以是字母、數(shù)字或者其他字符串，串中字符的個(gè)數(shù)n稱為串的長(zhǎng)度。n=0時(shí)的串稱為空串。

ps：不同的編程語(yǔ)言對(duì)字符串的引號(hào)規(guī)定不同，java和c是雙引號(hào)，python是單引號(hào)

子串：串中任意個(gè)連續(xù)的字符組成的子序列

主串：包含子串的串。

字符在主串中的位置：字符在串中的序號(hào)（需要注意的是，字符編號(hào)從1開(kāi)始）

子串在主串中的位置：子串的第一個(gè)字符在主串中的位置

空串vs空格串：如下圖，M的單引號(hào)里面啥也沒(méi)有，是一個(gè)空串，長(zhǎng)度為0。而N兩個(gè)單引號(hào)之間是有幾個(gè)空格字符的（我們這里是打了三個(gè)空格），所以N這個(gè)字符串，它的長(zhǎng)度是3而不是0

字符串這種數(shù)據(jù)結(jié)構(gòu)，它的邏輯特性看起來(lái)和我們之前學(xué)習(xí)的線性表非常相似，線性表也是由多個(gè)數(shù)據(jù)元素組成的有序序列，事實(shí)上，串也是一種特殊的線性表

串和線性表區(qū)別就是：普通的線性表，里面存放的數(shù)據(jù)元素可以是各種各樣的數(shù)據(jù)類型，而串（字符串）這種數(shù)據(jù)結(jié)構(gòu)，它的各個(gè)數(shù)據(jù)元素一定是字符

1.1.2串的基本操作

StrAssign(&T,chars):賦值操作，把串T賦值為chars

StrCopy(&T,S):復(fù)制操作，由串S復(fù)制得到串T

StrEmpty(S):判空操作，若S為空串返回True，否則返回False

StrLength(S):求串長(zhǎng)，返回串S的元素個(gè)數(shù)

ClearString(&S):清空操作，將S清為空串

DestroyString:銷毀串，將串S銷毀（回收存儲(chǔ)空間）

Concat(&T,S1,S2):串聯(lián)接，用T返回由S1,S2聯(lián)接組成的新串

SubString(&Sub,S,pos,len):求子串，用Sub返回串S的第pos個(gè)字符起長(zhǎng)度為len的子串

Index(S,T):定位操作，若主串S中存在與串T值相同的子串，返回它在主串S中第一次出現(xiàn)的位置，否則函數(shù)值為0

StrCompare(S,T):比較操作。若S>T，則返回值>0；若S=T，則放值=0；若S<T，則返回值<0

1.1.3小結(jié)

1.2串的存儲(chǔ)結(jié)構(gòu)

1.2.1順序存儲(chǔ)

//靜態(tài)數(shù)組實(shí)現(xiàn)（定長(zhǎng)順序存儲(chǔ)）
#define  MAXLEN 255 //預(yù)定義最大串長(zhǎng)為255
typedef struct{
    char ch[MAXLEN];//每個(gè)分量存儲(chǔ)一個(gè)字符
    int length;//串實(shí)際長(zhǎng)度
}SString;

如果用這種方式，當(dāng)你聲明一個(gè)靜態(tài)的字符串，系統(tǒng)會(huì)為你開(kāi)辟如下空間來(lái)存放你的各個(gè)字符，每個(gè)字符（char類型）占1字節(jié)。當(dāng)然了，也需要一小片空間來(lái)存放length變量。

而我們知道，這種靜態(tài)數(shù)組的缺點(diǎn)就是數(shù)組長(zhǎng)度不可變。我們現(xiàn)在預(yù)設(shè)的大小是255，如果后面遇到長(zhǎng)度大于255的，存不下了，想拓展這個(gè)數(shù)組是不可能的。所以我們又稱之為定長(zhǎng)的順序存儲(chǔ)（本身還是一個(gè)靜態(tài)數(shù)組，和線性表一樣），該中方式，內(nèi)存空間在使用結(jié)束系統(tǒng)會(huì)自動(dòng)回收。

如果想實(shí)現(xiàn)可變大小，就可以用動(dòng)態(tài)數(shù)組的方式來(lái)實(shí)現(xiàn)，也就是在你的結(jié)構(gòu)體里面定義一個(gè)基地址的指針，然后用malloc申請(qǐng)一整片連續(xù)的存儲(chǔ)空間，讓基地址指針指向這片空間的起始地址。

//動(dòng)態(tài)數(shù)組實(shí)現(xiàn)（堆分配存儲(chǔ)）
typedef struct{
    char *ch;//按串長(zhǎng)分配存儲(chǔ)區(qū)，ch指向串的基地址
    int length;//串的長(zhǎng)度
}HString;

HString S;
S.ch=(char*)malloc(MAXLEN*sizeof(char));
S.length=0;

需要注意的是，malloc函數(shù)申請(qǐng)的內(nèi)存空間屬于堆區(qū)，所以這周實(shí)現(xiàn)方式又稱為堆分配存儲(chǔ)（本身還是一個(gè)動(dòng)態(tài)數(shù)組）

堆區(qū)的內(nèi)存空間，你需要手動(dòng)的free掉之前malloc的空間

下面是串順序存儲(chǔ)的4個(gè)實(shí)現(xiàn)方案

ps:對(duì)于方案二，雖然是節(jié)省了末尾的一個(gè)空間，但是由于char[0]作為存儲(chǔ)長(zhǎng)度的空間，char類型只有1字節(jié)，也就是8比特位，所以只能存儲(chǔ)0-255的數(shù)，如果字符串長(zhǎng)超過(guò)就會(huì)有問(wèn)題了。

教材中的方案4，是方案1和方案2的結(jié)合，我們舍棄char[0]的位置，這樣第i個(gè)數(shù)正好對(duì)應(yīng)i下標(biāo)。而且用int類型的length存儲(chǔ)字符串長(zhǎng)度范圍會(huì)比char類型存儲(chǔ)長(zhǎng)度更大。

1.2.2鏈?zhǔn)酱鎯?chǔ)

鏈?zhǔn)酱鎯?chǔ)和線性表也一樣的，如下

typedef struct StringNode{
    char ch;//每個(gè)結(jié)點(diǎn)存1個(gè)字符
    struct StringNode *next;
}StringNode,*String;

我們用每一個(gè)如上的結(jié)點(diǎn)來(lái)存一個(gè)字符和一個(gè)指針來(lái)指向下一結(jié)點(diǎn)。需要注意的是，我們這里一個(gè)char是一個(gè)字符，char大小只有1字節(jié)，但是一個(gè)指針大小4字節(jié)。這就意味著，你用1字節(jié)空間存儲(chǔ)實(shí)際想要的信息，卻還要花4字節(jié)空間存儲(chǔ)一個(gè)輔助信息，這種情況就稱為存儲(chǔ)密度低
ps：存儲(chǔ)密度低也就是實(shí)際有用的信息所占的比例非常小

如何解決存儲(chǔ)密度低的問(wèn)題呢？我們可以讓每一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，如下：

typedef struct StringNode{
    char ch[4];//每個(gè)結(jié)點(diǎn)存多個(gè)字符
    struct StringNode* next;
}StringNode,*String;

這里是結(jié)點(diǎn)中定義的是ch[4]，也就是每個(gè)結(jié)點(diǎn)存4字符，你也可以改成別的數(shù)字，讓一個(gè)結(jié)點(diǎn)存的更多。

這樣的話，每個(gè)結(jié)點(diǎn)中實(shí)際有用的信息所占的空間比例就高了，即存儲(chǔ)密度提高了。所以，如果要用鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)串，一般來(lái)說(shuō)推薦該中方式。

1.2.3基于順序存儲(chǔ)實(shí)現(xiàn)基本操作

我們著重介紹接下來(lái)的幾個(gè)重要的操作：

SubString(&Sub,S,pos,len):求子串，用Sub返回串S的第pos個(gè)字符開(kāi)始，長(zhǎng)度為len的子串

舉個(gè)例子，如下圖我們存儲(chǔ)了wangdao這七個(gè)字符串，我們傳pos=4，len=3過(guò)去，也就是要4號(hào)下標(biāo)，長(zhǎng)度為3的子串gda，如下圖：

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;
//求子串
bool SubString(SString &Sub,SString S,int pos,int len){
    //子串范圍越界
    if(pos+len-1>S.length)
       return false;
    for(int i=pos;i<pos+len;i++)
    {
        Sub.ch[i-pos+1]=S.ch[i];
    }
    Sub.length=len;
    return true;
}

StrCompare(S,T):比較操作，若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<0；

如何比較兩個(gè)字符串大??？比如有兩個(gè)字符串S和T，從它們第一個(gè)字符開(kāi)始比較，如果相同則比較它們下一個(gè)字符，如果不相同，則哪個(gè)字符大哪個(gè)字符串就大——先出現(xiàn)更大字符的那個(gè)字符串更大，還有一種情況就是兩個(gè)字符串掃描過(guò)的字符都相同則長(zhǎng)度長(zhǎng)的串更大，比如abc和abcd，abcd更大

//比較操作，若S>T，則返回值>0；若S=T，則返回值=0；若S<T，則返回值<0；
int StrCompare(SString S,SString T){
    for(int i=1;i<S.length&&i<=T.length;i++)
    {
        if(S.ch[i]!=T.ch[i])
           return S.ch[i]-T.ch[i];
    }
    //掃描過(guò)的所有字符都相同，則長(zhǎng)度大的串更大
    return S.length-T.length;
}

Index(S,T):定位操作，若主串S中存在與串T值相同的子串，則返回它在主串S中第一次出現(xiàn)的位置，否則函數(shù)值為0

怎么確定位置呢？舉個(gè)例子，我們現(xiàn)在有S和T兩個(gè)字符串，要在主串S中找出串T相同的子串：

假設(shè)S和T如下，T長(zhǎng)度為3：

我們可以用剛才實(shí)現(xiàn)的兩個(gè)基本操作，用第一個(gè)取子串的操作，我們從主串S中取下長(zhǎng)度為3的子串，如下

再用剛才講的比較操作，看從S中取下的子串是否與T相等
如果不等，我們就在S中往后一位，繼續(xù)取長(zhǎng)度為3的子串與T對(duì)比

然后以此類推，直到在S中找到一個(gè)子串和T相等，然后返回子串第一個(gè)字符的位序即可。

int Index(SString S,SString T){
    int i=1,n=StrLength(S),m=StrLength(T);
    SString sub;//用于暫存子串
    while(i<=n-m+1){
        SubString(sub,S,i,m);
        if(StrCompare(sub,T)!=0){
           i++;
        }
        else{
           return i;//返回子串在主串中的位置
        }
    }
    return 0;//S中不存在與T相等的子串
}

1.2.4小結(jié)

二、串的模式匹配

2.1什么是字符串的模式匹配

模式匹配算法聽(tīng)起來(lái)好像很nb，其實(shí)并沒(méi)有什么。我們來(lái)看兩個(gè)例子就知道啥是模式匹配了。

你用word文檔的時(shí)候，是不是經(jīng)常使用一個(gè)搜索功能：就是你輸入一段文字，然后word給你搜這段文字。

還有就是你用搜索引擎的時(shí)候，是不是也經(jīng)常會(huì)輸入一段文字，然后搜索引擎給你在網(wǎng)頁(yè)里面匹配和這個(gè)文章相同的子串。

這就是字符串的匹配模式，其實(shí)就是要在字符串里面搜索某一段內(nèi)容

從一整段字符串中搜索內(nèi)容，被搜索的字符串我們稱為主串。
而我們想搜索的內(nèi)容，稱為模式串，需要注意，模式串不一定能在主串中找到。
子串：是主串的一部分，是一定可以在主串中找到的。

所謂字符串的模式匹配，就是指我們?cè)谥鞔姓业脚c模式串相同的子串，并返回子串的位置。

2.2樸素模式匹配算法

既然它都說(shuō)是樸素了嘛，樸素的宗旨就是最簡(jiǎn)單，就是暴力解決。

比如我們下面兩個(gè)字符串：主串S和模式串T

模式串T長(zhǎng)度是6，我們就把主串中所有長(zhǎng)度為6的子串與它進(jìn)行比較唄。

我們從主串中找出第一個(gè)長(zhǎng)度為6的子串，該子串和模式串進(jìn)行對(duì)比，如果不匹配，就再對(duì)比下一個(gè)。如果下一個(gè)子串還不匹配，就再下一個(gè)，以此類推。。。。

我們把所有的這些子串都和模式串進(jìn)行一個(gè)對(duì)比，這樣肯定是沒(méi)有遺漏的進(jìn)行一個(gè)匹配了。但是也有可能當(dāng)我們對(duì)比完最后一個(gè)子串發(fā)現(xiàn)沒(méi)有子串和模式串匹配，這種情況就是匹配失敗。

長(zhǎng)度為n的主串，長(zhǎng)度為m的子串有n-m+1個(gè)

學(xué)的比較扎實(shí)的同學(xué)會(huì)發(fā)現(xiàn)，我們之前學(xué)習(xí)串的Index函數(shù)不就是樸素模式匹配的思想嗎？如下圖：

接下來(lái)我們將介紹，如何直接通過(guò)操作數(shù)組下標(biāo)來(lái)實(shí)現(xiàn)樸素模式匹配算法：
現(xiàn)有主串S和模式串T：

我們?cè)O(shè)置兩個(gè)掃描指針i和j，這兩個(gè)指針指到哪，我們就把字符對(duì)比到哪

如上動(dòng)態(tài)圖所示，剛開(kāi)始要對(duì)比的就是主串的第一個(gè)字符和模式串的第一個(gè)字符，如果這兩個(gè)字符相等，就讓i和j往后移。然后重復(fù)進(jìn)行比較和后移操作，直到我們發(fā)現(xiàn)最后一個(gè)位置i和j指向的字符不等。

不等就說(shuō)明匹配失敗了，第一個(gè)子串和這個(gè)模式串是沒(méi)有匹配上的，那么我們就該匹配第二個(gè)子串位置了，而第二個(gè)子串的起始位置應(yīng)該是在2號(hào)位

所以，在我們處理時(shí)，如果發(fā)現(xiàn)當(dāng)前的子串匹配失敗，那么我們主串的掃描指針i應(yīng)該讓它指向下一個(gè)子串的第一個(gè)位置，而模式串的指針j應(yīng)該回到模式串的第一個(gè)位置。
寫成代碼就是i=i-j+2; j=1;
j當(dāng)前的值說(shuō)明了我們現(xiàn)在匹配到了子串的第幾個(gè)字符，我們讓i-j就得到了目前子串的前一個(gè)位置，再+2就是下一個(gè)子串的第一個(gè)位置。

因此，當(dāng)前子串匹配失敗后i=i-j+2,i會(huì)變成2，而j會(huì)變成1。

然后就是開(kāi)始匹配第二個(gè)子串和模式串T，發(fā)現(xiàn)第2個(gè)字符就不一樣

匹配第三個(gè)子串，發(fā)現(xiàn)第2個(gè)字符不一樣

匹配第四個(gè)子串，發(fā)現(xiàn)六個(gè)字符都可以匹配成功，因?yàn)槊看纹ヅ涑晒++; j++，所以此時(shí)j會(huì)超出模式串的長(zhǎng)度

所以，若j>T.Length，則當(dāng)前子串匹配成功，返回當(dāng)前子串第一個(gè)字符的位置，也就是i-T.Length

我們這里給出樸素模式算法的代碼實(shí)現(xiàn)：

int Index(SString S,SString T){
    int i=1;j=1;
    while(i<=S.length&&j<=T.length){
        if(S.ch[i]==T.ch[j]){
            i++;//繼續(xù)比較后續(xù)字符
            j++;
        }
        else{
            i=i-j+2;//指針后退后重新開(kāi)始匹配
            j=1; 
        }
    }
    if(j>T.Length)
       return i-T.Length;
    else
       return 0;
}

下面來(lái)分析一下該算法的最壞時(shí)間復(fù)雜度：假設(shè)主串長(zhǎng)度為n，模式串長(zhǎng)度m

如下例：主串S和模式串T都是除了最后一個(gè)是b其他全是a，

按照樸素模式匹配算法的規(guī)則，我們得先匹配主串第一個(gè)子串和模式串，一個(gè)字符一個(gè)字符依次往后對(duì)比。你會(huì)發(fā)現(xiàn)前面的字符都可以匹配，但是比到最后一個(gè)字符就匹配失敗了。

接下來(lái)比較第二個(gè)字符串，讓i到2的位置，j到1的位置。然后依次比較，又是到最后一個(gè)字符才發(fā)現(xiàn)比較失敗。


后面以此類推，每個(gè)子串都要比較m個(gè)字符，一共n-m+1子串,時(shí)間復(fù)雜度O（(n-m+1)*m）=O(nm)

2.3KMP算法

上小節(jié)我們學(xué)習(xí)了樸素模式匹配算法，KMP算法其實(shí)就是基于樸素模式匹配算法的優(yōu)化。

舉個(gè)例子：

現(xiàn)假設(shè)我們第一個(gè)子串在第六個(gè)字符匹配失敗，那我們按照樸素模式匹配算法是不是就該匹配第二個(gè)子串了？

但是樸素模式匹配忽略了一個(gè)重要的信息：如果是第6個(gè)字符匹配失敗，那么前5個(gè)字符一定是匹配成功的。

那么進(jìn)入第二個(gè)子串的匹配：我們由第一個(gè)子串知道，第二個(gè)子串第1個(gè)字符是b，那么與模式串T第一個(gè)字符不匹配。那么第二個(gè)字符的第5個(gè)字符（圖中6號(hào)位置）和第6個(gè)字符（圖中7號(hào)位置）在本輪匹配中也就不用檢查了

進(jìn)入第三個(gè)子串的匹配：我們知道第三個(gè)子串第二個(gè)字符與模式串不匹配，后面也不用檢查了。

進(jìn)入第四個(gè)子串的匹配：我們發(fā)現(xiàn)第四個(gè)子串前兩個(gè)已知的字符都是可以匹配的，那么就需要進(jìn)行檢查第四個(gè)子串的第3-6個(gè)字符了（圖中6號(hào)下標(biāo)到9號(hào)下標(biāo)）

---------------------------我是分隔符------------------------------------

再來(lái)捋一遍：當(dāng)我們匹配到某一個(gè)字符，該字符發(fā)生了失配。該字符前面的字符信息我們是可以確定的，它和模式串一定是保持一致的。

比如我們模式串a(chǎn)baabc，那么第一個(gè)子串第6個(gè)字符失配，我們就可以確定前5個(gè)字符為abaab，那么以第二個(gè)元素開(kāi)頭的子串和以第三個(gè)元素開(kāi)頭的子串就不用匹配了，直接匹配第四個(gè)元素開(kāi)頭的子串。
現(xiàn)確定主串S前5個(gè)元素為abaab
如果是第二個(gè)元素開(kāi)頭的子串，第一個(gè)字母是b，與模式串第一個(gè)字符a不匹配
如果是第三個(gè)元素開(kāi)頭的子串，前兩個(gè)字母是aa，與模式串前兩個(gè)字符ab不匹配

而對(duì)于第四個(gè)子串來(lái)說(shuō)，我們也沒(méi)必要對(duì)比第四個(gè)子串的前兩個(gè)字符，因?yàn)槲覀兛梢源_定這兩個(gè)元素肯定是和模式串能匹配的

現(xiàn)在暫時(shí)還不能確定的是我們模式串的第三元素和主串里面剛才失配的元素是否匹配

因此對(duì)于模式串T='abaabc’來(lái)說(shuō)，當(dāng)?shù)?個(gè)元素匹配失敗時(shí)，可令主串指針i不變，模式串指針j=3，也就是從模式串的第三個(gè)元素開(kāi)始匹配。

因此可以看到，我們利用好模式串本身的信息，可以跳過(guò)很多沒(méi)必要的對(duì)比。對(duì)于當(dāng)前的模式串和主串來(lái)說(shuō)，我們是跳過(guò)了中間的幾個(gè)子串，也跳過(guò)了第四個(gè)子串前兩個(gè)字符，直接從第四個(gè)子串第三字符開(kāi)始比較，如下圖：

這就是KMP算法的思想，要利用好模式串本身隱含的一些信息，然后要確定模式串某個(gè)元素發(fā)生失配時(shí)，我們要如何處理。

顯然，這里得到的結(jié)論并不依賴于主串，只和模式串有關(guān)。和我們匹配的是主串的哪個(gè)位置并沒(méi)有關(guān)系

再來(lái)具體應(yīng)用一下，如果我們現(xiàn)在從主串的第五個(gè)位置開(kāi)始嘗試匹配。同樣的，我們匹配到該子串最后一個(gè)元素時(shí)發(fā)生失配，我們可以知道前面幾個(gè)字符肯定是一樣的


那么根據(jù)剛才的結(jié)論，第六個(gè)字符失配時(shí)，主串指針i不變，模式串指針j變成3

也就是直接跳過(guò)了中間幾個(gè)子串的對(duì)比，然后當(dāng)前這個(gè)子串也是從第三個(gè)元素開(kāi)始往后匹配。

因?yàn)閯偛虐l(fā)生失配的元素到底是什么我們不知道，因此，它有可能和我們模式串第三個(gè)元素能匹配上。

到這里，我們探討的是這個(gè)模式串的第六個(gè)元素發(fā)生失配的情況我們?cè)撛趺崔k，接下來(lái)順著這個(gè)思路我們把其他情況考慮一下。

對(duì)于模式串T=‘a(chǎn)baabc’，當(dāng)?shù)?個(gè)元素匹配失敗，怎么辦？
第五個(gè)元素發(fā)生失配，那么前面4個(gè)元素信息我們是知道的


那么第二個(gè)子串能否匹配呢？顯然也是不可以的，第二個(gè)子串第一個(gè)元素就失敗了

再看第三個(gè)子串，第三個(gè)子串第二個(gè)元素匹配失敗

再看第四個(gè)子串，發(fā)現(xiàn)前面已知的信息是可以匹配上的。

而剛才發(fā)生失配的字符我們不知道是什么，所以我們接下來(lái)從圖中5號(hào)位置開(kāi)始往后比較即可。

因此對(duì)于模式串T='abaabc’來(lái)說(shuō)，當(dāng)?shù)?個(gè)元素匹配失敗時(shí)，可令主串指針i不變，模式串指針j=2，也就是從模式串的第二個(gè)元素開(kāi)始匹配。

對(duì)于模式串T=‘a(chǎn)baabc’，當(dāng)?shù)?個(gè)元素匹配失敗，怎么辦？
第四個(gè)元素匹配失敗，前面3個(gè)元素的信息我們是可以知道的

看第二個(gè)子串，發(fā)現(xiàn)第一個(gè)元素就無(wú)法匹配

看第三個(gè)子串，發(fā)現(xiàn)已知的信息是可以和模式串匹配的。

接下來(lái)我們就從模式串j=2的位置往后匹配即可

因此對(duì)于模式串T='abaabc’來(lái)說(shuō)，當(dāng)?shù)?個(gè)元素匹配失敗時(shí)，可令主串指針i不變，模式串指針j=2，也就是從模式串的第二個(gè)元素開(kāi)始匹配。

對(duì)于模式串T=‘a(chǎn)baabc’，當(dāng)?shù)?個(gè)元素匹配失敗，怎么辦？

第三個(gè)元素失配，那么前兩個(gè)元素信息是已知的


看第二個(gè)子串能否匹配，發(fā)現(xiàn)第一個(gè)元素就無(wú)法匹配

看第三個(gè)子串能否匹配，發(fā)現(xiàn)沒(méi)有已知信息了。所以要從第三個(gè)子串第一個(gè)元素往后匹配

因此對(duì)于模式串T='abaabc’來(lái)說(shuō)，當(dāng)?shù)?個(gè)元素匹配失敗時(shí)，可令主串指針i不變，模式串指針j=1，也就是從模式串的第一個(gè)元素開(kāi)始匹配。

對(duì)于模式串T=‘a(chǎn)baabc’，當(dāng)?shù)?個(gè)元素匹配失敗，怎么辦？

第二個(gè)元素失配，我們只知道第一個(gè)元素信息

所以我們只能把下一個(gè)子串和模式串進(jìn)行對(duì)比

因此對(duì)于模式串T='abaabc’來(lái)說(shuō)，當(dāng)?shù)?個(gè)元素匹配失敗時(shí)，可令主串指針i不變，模式串指針j=1，也就是從模式串的第一個(gè)元素開(kāi)始匹配。

對(duì)于模式串T=‘a(chǎn)baabc’，當(dāng)?shù)?個(gè)元素匹配失敗，怎么辦？
那就直接下一個(gè)子串進(jìn)行匹配唄！

和之前的幾種情況不同的是，剛才的某個(gè)元素發(fā)生失配我們的主串指針i是不變的，j改變。

代碼中怎么操作？我們先讓j=0，也就是指向模式串第一個(gè)元素前一個(gè)位置，然后i和j統(tǒng)一++


然后對(duì)比后面的子串即可。

到這里，我們對(duì)于模式串T=‘a(chǎn)baabc’來(lái)說(shuō)，它的每一個(gè)元素發(fā)生失配的情況我們就全考慮進(jìn)去了

這種方式，我們主串的指針i一直往下走一遍就行了，不需要樸素模式中那種還要回頭匹配，比樸素模式匹配效率高了非常多。

在模式匹配中，通常模式串是很短的，而主串可能非常的長(zhǎng)，那么用我們這種策略，先分析模式串中的隱藏信息，再去進(jìn)行匹配，非常高效！

而對(duì)于剛才的指針j的變化操作，我們可以用一個(gè)next數(shù)組來(lái)存儲(chǔ)相關(guān)信息：
比如當(dāng)?shù)诹鶄€(gè)元素發(fā)生失配時(shí)，我們讓j=3，對(duì)應(yīng)數(shù)組信息就是next[6]=3

再比如當(dāng)?shù)谖鍌€(gè)元素發(fā)生失配時(shí)，我們讓j=2，對(duì)應(yīng)數(shù)組信息就是next[5]=2

next數(shù)組就是指明了我們?cè)谀骋粋€(gè)位置發(fā)生失配時(shí)，應(yīng)該把j的值修改為多少。而比較特殊的是第一個(gè)元素就發(fā)生失配時(shí)，需要先把j修改為0，然后i和j統(tǒng)一++

我們的next數(shù)組是和模式串的值相關(guān)的，與主串無(wú)關(guān)。
所以，KMP算法的整體流程為：在進(jìn)行模式匹配前，先進(jìn)行一個(gè)預(yù)處理，要分析模式串，然后求出和模式串對(duì)應(yīng)的next數(shù)組，然后再利用next數(shù)組進(jìn)行模式匹配，整個(gè)匹配流程中，主串的指針i不需要回溯。

下一小節(jié)我們介紹如何求next數(shù)組，這里先學(xué)習(xí)如何利用next數(shù)組進(jìn)行匹配

int Index_KMP(SString S,SString T,int next[]){
    int i=1;j=1;
    while(i<=S.length&&j<T.length){
        if(j==0||S.ch[i]==T.ch[j]){
           i++;
           j++;//繼續(xù)比較后續(xù)字符
        }
        else
           j=next[j];//模式串向右移動(dòng)
    }
    if(j>T.length)
       return i-T.length;//匹配成功
    else
       return 0;
}

2.4求next數(shù)組

根據(jù)上小節(jié)的學(xué)習(xí)，我們知道了kmp算法的原理，首先我們需要根據(jù)模式串的值，求出與這個(gè)模式串相應(yīng)的next數(shù)組，接下來(lái)基于這個(gè)next數(shù)組，來(lái)對(duì)模式串進(jìn)行匹配。整個(gè)匹配的過(guò)程，主串的指針不回溯。

本節(jié)將介紹幾個(gè)求next數(shù)組的例子，來(lái)幫大家達(dá)到手算next數(shù)組的水準(zhǔn)。

比如現(xiàn)在有g(shù)oogle這一個(gè)字符串，其長(zhǎng)度為6，我們創(chuàng)建一個(gè)next數(shù)組，next[j]表示模式串中第j個(gè)字符發(fā)生匹配失敗時(shí)，指針j應(yīng)該指向什么位置。

如果現(xiàn)在第1個(gè)字符匹配失?。?/font>

按照上小節(jié)分析的邏輯，應(yīng)該是讓j指針先等于0，然后i++,j++


任何模式串都一樣，第一個(gè)字符不匹配時(shí)，只能匹配下一個(gè)子串，因此next[1]無(wú)腦寫0即可

nextval[1]=0;
for (int j=2;j<T.length;j++){
  if(T.ch[next[j]]==T.ch[j])
  {
     nextval[j]=nextval[next[j]];
  }
  else
  {
     nextval[j]=next[j];
  }
}