4.3.1 求子串位置的定位函數(shù)Index(S,T,pos)

子串的定位操作通常稱做串的模式匹配（其中T稱為模式串），采用定長順序存儲結(jié)構(gòu)，可以寫出不依賴于其他串操作的匹配算法。

算法4.5：

下面是書中的偽代碼：

int Index(SString S, SString T, int pos) { // 返回子串T在主串S中第pos個字符之后的位置。// 若不存在，則函數(shù)值為0。// 其中，T非空，1≤pos≤StrLength(S)。int i = pos;int j = 1;while (i <= S[0] && j <= T[0]) {if (S[i] == T[j]) // 繼續(xù)比較后繼字符{ ++i;++j;}else // 指針后退重新開始匹配 {i = i - j + 2;j = 1;}}if (j > T[0]) return i - T[0];else return 0; } // Index

下面分析下：

這里先說明下，這個S[0],T[0]這個地方存儲了整個串的大小。

這個代碼的巧妙之處在于i=i-j+2和j=1這個地方，這個i=j-j+2，可以讓i進行后移，也就是S后移，這里j=1,的意思如下：舉個例子，當T中是ABC，而S是ABABABC，pos為1，那么j=1的作用就是清理，什么叫清理，意思就是當發(fā)現(xiàn)S中只有前兩個字母相似，而沒有第三個，這時重新計數(shù)。當然i也要進行回溯。

下面這張圖，提現(xiàn)了這個過程（T='abcac'和主串S,pos=1）

這節(jié)就到這，下一節(jié)講解數(shù)據(jù)結(jié)構(gòu)里面的第一個難點：

KMP算法！

總結(jié)

以上是生活随笔為你收集整理的4.3串的模式匹配算法（BF算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。