串運算的實現

子串定位運算

　　串是特殊的線性表故順序串和鏈串上實現的運算分別與順序表和單鏈表上進行的操作類似
　　C語言的串庫<stringh>裡提供了豐富的串函數來實現各種基本運算因此我們對各種串運算的實現不作討論利用串函數實現串的基本運算部分內容【參見練習】
　　下面討論在順序串和鏈串上實現的子串定位運算

子串定位運算
　　子串定位運算類似於串的基本運算中的字符定位運算只不過是找子串而不是找字符在主串中首次出現的位置此運算的應用非常廣泛
　　【例】在文本編輯中我們經常要查找某一特定單詞在文本中出現的位置解此問題的有效算法能極大地提高文本編輯程序的響應性能
　　子串定位運算又稱串的模式匹配或串匹配

目標（串）和模式（串）
　　在串匹配中一般將主串稱為目標（串）子串稱為模式（串）
　　假設T 為目標串P為模式串且不妨設
              T=ttt…tn
              P=ppp…pm(＜m≤n)

串匹配
　　串匹配就是對於合法的位置（又稱合法的位移）≤i≤nm依次將目標串中的子串titi+…ti+m和模式串ppp…pm進行比較
　　①若titi+…ti+m＝ppp…pm則稱從位置i開始的匹配成功或稱i為有效位移
　　②若titi+…ti+m≠ppp…pm則稱從位置i開始的匹配失敗或稱i為無效位移
　　因此串匹配問題可簡化為找出某給定模式串P在給定目標串T中首次出現的有效位移
　　　注意
　　有些應用中要求求出P在T中所有出現的有效位移

順序串上的子串定位運算
（）樸素的串匹配算法的基本思想
    　即用一個循環來依次檢查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<m&&Tch[k]==Pch[j]{
                           k++;j++;
                   }
                    if(j==m)  //既T[ii+m]=P[m]
                          return i;  //i為有效位移否則查找下一個位移
               }//endfor
               return ;  //找不到有效位移匹配失敗
           }//NaiveStrMatch

（）算法分析
①最壞時間復雜度
　　該算法最壞情況下的時間復雜度為O((nm+)m)
　　分析當目標串和模式串分別是anb和amb時對所有nm+個合法的位移均要比較m個字符才能確定該位移是否為有效位移因此所需比較字符的總次數為（nm+）m

②模式匹配算法的改進
　　樸素的串匹配算法雖然簡單但效率低其原因是在檢查位移i是否為有效位移時沒有利用檢查位移ii…時的部分匹配結果
　　若利用部分匹配結果模式串右滑動的距離就不會是每次一位而是每次使其向右滑動得盡可能遠這樣可使串匹配算法的最壞時間控制在O（m+n）數量級上具體可【參閱有關文獻】

鏈串上的子串定位運算
　　用結點大小為的單鏈表做串的存儲結構時實現樸素的串匹配算法很簡單只是現在的位移shift是結點地址而非整數且單鏈表中沒有存儲長度信息若匹配成功則返回有效位移所指的結點地址否則返回指針具體算法如下
      LinkStrNode *LinkStrMatch(LinkString TLinkString 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/22622.html