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

　　子串定位運算

　　串是特殊的線性表故順序串和鏈串上實現的運算分別與順序表和單鏈表上進行的操作類似

　　C語言的串庫裡提供了豐富的串函數來實現各種基本運算因此我們對各種串運算的實現不作討論利用串函數實現

　　串的基本運算部分內容【參見練習】

　　下面討論在順序串和鏈串上實現的子串定位運算

　　子串定位運算

　　子串定位運算類似於串的基本運算中的字符定位運算只不過是找子串而不是找字符在主串中首次出現的位置此運算的應用非

　　常廣泛

　　【例】在文本編輯中我們經常要查找某一特定單詞在文本中出現的位置解此問題的有效算法能極大地提高文本編輯程序的

　　響應性能

　　子串定位運算又稱 串的模式匹配 或 串匹配

　　目標(串)和模式(串)

　　在串匹配中一般將主串稱為 目標(串) 子串稱為 模式(串)

　　假設T 為目標串P為模式串且不妨設

　　T=t t t …t n

　　P=p p p …p m (

　　3、串匹配

　　串匹配就是對於 合法的位置 (又稱合法的位移)0≤i≤n-m，依次將目標串中的子串"t i t i+1 …t i+m-1 "和模式串"p 0

　　p 1 p 2 …p m-1 "進行比較：

　　①若"t i t i+1 …t i+m-1 "="p 0 p 1 p 2 …p m-1 "，則稱從位置i開始的匹配成功，或稱i為 有效位移 。Tw.wINgwIT.CoM

　　②若"t i t i+1 …t i+m-1 "≠"p 0 p 1 p 2 …p m-1 "，則稱從位置i開始的匹配失敗，或稱i為 無效位移 。

　　因此，串匹配問題可簡化為找出某給定模式串P在給定目標串T中首次出現的有效位移。

　　注意：

　　有些應用中要求求出P在T中所有出現的有效位移。

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