順序串上的子串定位運算
子串定位又稱串的模式匹配（Pattern Matching）或串匹配（String Matching）
在串匹配中一般將主串稱為目標（串）子串稱為模式（串）
假設T為目標串P為模式串且設
T=tt…tn P=pp…pm (＜m≤n)
用T[ij]表示T的子串titi+…tj(≤i≤j≤n)用P[ij]表示P的子串pipi+…pj(≤i≤j≤m)
串匹配實際上是對於合法的位置≤i≤nm依次將目標串中的子串T[ii+m]和模式串P[m]進行比較若T[ii+m]=P[m]（即titi+…ti+m=pp…pm）則稱從位置i開始的匹配成功亦稱模式P在目標T中出現若T[ii+m]≠P[m]（即存在某個≤j≤m使得ti+j≠pj）則稱從位置i開始的匹配失敗
上述的位置i又稱為位移當T[ii+m]=p[m]時i稱為有效位移當T[ii+m]≠p[m]時i稱為無效位移
樸素的串匹配算法
基本思想用一個循環來依次檢查nm+個合法的位移i（≤i≤nm）是否為有效位移
該算法至多匹配nm+次每匹配要做m次比較故算法至多比較m*(nm+)次時間復雜性為O((nm+)*m)通常情況下m的值遠小於n的值時間復雜性可粗略地記為O(n*m)
鏈串上的子串定位運算
位移shift是結點地址而非整數且單鏈表中沒有存儲長度信息若匹配成功則返回有效位移所指的結點地址否則返回空指針
該算法的時間復雜度與順序串上樸素的串匹配算法相同
From:http://tw.wingwit.com/Article/program/sjjg/201311/23311.html
