數據結構-基于Python語言（微課版） 課件T9-串(模式匹配)

模式匹配第四章：串

主講：周翔樸素的模式匹配算法（BF算法）樸素的模式匹配算法思路：從主串s的第一個字符開始與t的第一個字符作比較；如果相等，繼續(xù)逐個比較后續(xù)的字符；如果不相等，使主串的第二個字符與t的第一個字符比較：如果相等，繼續(xù)逐個比較后續(xù)的字符；如果不相等，使主串的第三個字符與t的第一個字符比較：………以此類推，直到主串s的一個連續(xù)子串序列與模式t相等，返回子串序列在s串中的位置；否則匹配不成功，返回-1。樸素的模式匹配算法（BF算法）樸素的模式匹配算法思路：abecdecd主串s子串t從主串s的第一個字符開始與t的第一個字符作比較不相等從主串s的第二個字符開始與t的第一個字符作比較不相等從主串s的第三個字符開始與t的第一個字符作比較相等繼續(xù)比較后面的字符相等繼續(xù)比較后面的字符相等匹配成功樸素的模式匹配算法（BF算法）樸素的模式匹配算法（BF算法）KMP算法KMP算法（無回溯的模式匹配）：KMP算法的主要思想就是利用已得到的部分匹配信息來進行后面的匹配過程，消除主串的回溯，從而提高匹配的效率。子串t主串scabxabeahycabdabKMP算法由匹配結果可以得出如下信息：t[0]=s[0]；t[1]=s[1]；t[0]!=t[1]==>t[0]!=s[1]；t[0]=s[0]；t[2]=s[2]；t[0]!=t[2]==>t[0]!=s[2]；t[0]=s[0]；t[3]=s[3]；t[0]=t[3]==>t[0]=s[3]；

t[1]=s[1]；t[4]=s[4]；t[1]=t[4]==>t[1]=s[4]；子串t主串scabxabeahycabdab因此下一次比較就比對s[5]與t[2]是否相等。這樣就省去了主串的回溯KMP算法KMP算法（無回溯的模式匹配）：對于t的每個字符t[j](0<=j<=m-1)，若存在一個整數k(k<j)，使得模式t中k所指字符前的k個字符(t0t1…tk-1)依次與tj的前面k個字符(tj-ktj-k+1…tj-1)相同，并與主串s中i所指字符之前的k個字符相同，那么利用這種匹配信息就可以避免不必要的回溯。在匹配之前，用一個數組next來存放模式串t中字符的匹配信息，通過分析t中的字符，得出匹配完當前字符后，下一次要匹配哪一個字符，將該字符信息存入next數組。存入next數組的這個值也稱為模式值、next值。KMP算法KMP算法（無回溯的模式匹配）：next值的推導規(guī)則如下所示：（1）next[0]=-1：任何串中第一個字符的模式值規(guī)定為-1；（2）next[j]=1：模式串t中下標為j的字符與首字符相同，且j之前的1-k個字符與開頭的1-k個字符不等（或者相等但t[k]=t[j]）（1<=k<j）；（3）next[j]=k：如果模式串t中下標為j的字符之前k個字符與t開頭的k個字符相等，且t[j]!=t[k]（1<=k<j），則next[j]=k；（4）next[j]=0：除（1）、（2）、（3）之外的其他情況next[j]都為0；KMP算法abcabd-100012bfbfbfkmpbf-10012340001KMP算法——分析總結本章主要講解了串的相關知識，包括串的概念、串的存儲結構、以及串常用的模