串 - 串的存儲結構 - 串運算的實現（二）

　　順序串上的子串定位運算

　　()樸素的串匹配算法的基本思想

　　即用一個循環來依次檢查nm+個合法的位移i(≤i≤nm)是否為有效位移

　　具體過程【 參見動畫演示 】

　　()順序串上的串匹配算法

　　以下以第二種定長的順序串類型作為存儲結構給出串匹配的算法

　　#define MaxStrSize //該值依賴於應用由用戶定義

　　typedef struct{

　　char ch[MaxStrSize]; //可容納個字符並依次存儲在ch[n]中

　　int length;

　　}SeqString;

　　int Naive StrMatch(SeqString TSeqString P)

　　{//找模式P在目標T中首次出現的位置成功返回第個有效位移否則返回

　　int ijk;

　　int m=Plength; //模式串長度

　　int n=Tlength; //目標串長度

　　for(i=;i<=nm;i++){ //<=i<=nm是合法的位移

　　j=;k=i; //下面用while循環判定i是否為有效位移

　　while(j

　　k++;j++;

　　}

　　if(j==m) //既T[i..i+m-1]=P[0..m-1]

　　return i; //i為有效位移，否則查找下一個位移

　　}//endfor

　　return -1; //找不到有效位移，匹配失敗

　　}//NaiveStrMatch

　　(3)算法分析

　　①最壞時間復雜度

　　該算法最壞情況下的時間復雜度為O((n-m+1)m)。TW.wiNgWIt.com

　　分析：當目標串和模式串分別是"a n-1 b"和"a m-1 b"時，對所有n-m+1個合法的位移，均要比較m個字符才能確定該位移是否為有

　　效位移，因此所需比較字符的總次數為(n-m+1)m。

　　②模式匹配算法的改進

　　樸素的串匹配算法雖然簡單，但效率低。其原因是在檢查位移i是否為有效位移時，沒有利用檢查位移i-1，i,…,0時的部分匹配

　　結果。

　　若利用部分匹配結果，模式串右滑動的距離就不會是每次一位，而是每次使其向右滑動得盡可能遠。這樣可使串匹配算法的最壞

　　時間控制在O(m+n)數量級上。具體可【參閱有關文獻】。

　　5、鏈串上的子串定位運算

　　用結點大小為1的單鏈表做串的存儲結構時，實現樸素的串匹配算法很簡單。只是現在的位移shift是結點地址而非整數，且單鏈

　　表中沒有存儲長度信息。若匹配成功，則返回有效位移所指的結點地址，否則返回指針。具體算法如下：

　　LinkStrNode *LinkStrMatch(LinkString T,LinkString P)

　　{//在鏈串上求模式P在目標T首次出現的位置

　　LinkStrNode * shift,*t,*p;

　　shift=T; //shift表示位移

　　t=shift;p=P;

　　while(t&&p) {

　　if(t->data==p->data){ //繼續比較後續結點中字符

　　t=t->next;

　　p=p->next;

　　}

　　else{ //已確定shift為無效位移

　　shift=shift->next; //模式右移，繼續判定shift是否為有效位移

　　t=shift;

　　p=P;

　　}

　　}//endwhile

　　if(p==NULL)

　　return shift; //匹配成功

　　else

　　return NULL; //匹配失敗

　　}

　　該算法的時間復雜度與順序表上樸素的串匹配算法相同。

From:http://tw.wingwit.com/Article/program/sjjg/201311/23903.html