4.4串的模式匹配算法 基本概念 1、模式匹配(定位) 设有主串S和子串T(将S称为目标串,将T称为模式 串),在主串S中,从位置 start开始查找,如若在主 串S中找到一个与子串T相等的子串,则返回T的第 个字符在主串中的位置,否则返回-1。 2、算法目的 确定主串中所含子串第一次出现的位置(定位) 3、算法种类 B算法(又称古典的、经典的、朴素的、穷举的) KMP算法
1 4.４ 串的模式匹配算法 一、基本概念 1、模式匹配（定位） 设有主串S和子串T（将S称为目标串，将T称为模式 串），在主串S中，从位置start开始查找，如若在主 串S中找到一个与子串T相等的子串，则返回T的第一 个字符在主串中的位置，否则返回-1。 2、算法目的 确定主串中所含子串第一次出现的位置（定位） 3、算法种类 BF算法 （又称古典的、经典的、朴素的、穷举的） KMP算法
Brute-Force算法 1、 Brute- Force算法的设计思想 将主串S的第一个字符和模式T的第1个字符比较, 若相等,继续逐个比较后续字符; 若不等,从主串S的下一字符起,重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式相等。返回值为S 中与T匹配的子序列第一个字符的序号,即匹配成功 否则,匹配失败,返回值-1。 2、 Brute- Force算法的实现 typedef struct i char str MaxSize; int length sTring;
2 二、Brute-Force算法 1、Brute-Force算法的设计思想： • 将主串S的第一个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串S的下一字符起，重新与T第一个字符比较。 • 直到主串S的一个连续子串字符序列与模式T相等。返回值为S 中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 –1。 2、 Brute-Force算法的实现 typedef struct { char str[MaxSize]; int length; }String;
int BFlndex(string S, int start, String T t int i=start,j=0,V: while(i<slength &&j< Tlength) i if(S str1==Tstr[D i++,j++, else +1;j=0 if =T length)Vi-Tlength else v=-1 return v
3 int BFIndex(String S, int start, String T) { int i = start, j = 0, v; while(i < S.length && j < T.length) { if(S.str[i] == T.str[j]) {i++; j++; } else{ i = i-j+1; j = 0; } } if (j==T.length) v=i-T.length; else v=-1; return v; }
3、BF算法的时间复杂度 讨论: 若n为主串长度,m为子串长度,则串的BF匹配算法最坏的情况 下需要比较字符的总次数为(n-m+1)m=O(m) 最好的情况是:一配就中!只比较了m次。 最恶劣情况是:主串前面n-m个位置都部分匹配到子串的最后 一位,即这nm位比较了m次,别忘了最后m位也各比较了 次,还要加上m!所以总次数为:(n-m)*m+m=(n- 影苦莉用己部分匹配过的信息而加快模式串的滑动速度? 能!而且主串S的指针必回溯!最坏情况也能达到o(n+m) 请看KMP算法!
4 3、BF算法的时间复杂度 讨论： 若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况 下需要比较字符的总次数为(n-m+1)*m＝O(n*m) 最好的情况是：一配就中！ 只比较了m次。 最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后 一位，即这n-m位比较了m次，别忘了最后m位也各比较了 一次，还要加上m！所以总次数为：(n-m)*m+m ＝(nm+1)*m 能否利用已部分匹配过的信息而加快模式串的滑动速度？ 能！而且主串S的指针i不必回溯！最坏情况也能达到O(n+m) 请看KMP算法！
KMP算法 KMP算法设计思想 尽量利用已经部分匹配的结果信息,尽量让不要回溯,加快模 式串的滑动速度。 例 a b a bca bcacba b' s=a b a b c a b ac b a b T=“ a bcac T=‘ a bc a c S=“ a ba bc a bc acb a b T=abc c k 需要讨论两个问题 ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k? ②模式应该向右滑多远才是高效率的?
5 尽量利用已经部分匹配的结果信息，尽量让i不要回溯，加快模 式串的滑动速度。 例： 三、KMP算法 １、KMP算法设计思想： S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ 需要讨论两个问题： ①如何由当前部分匹配结果确定模式向右滑动的新比较起点k？ ② 模式应该向右滑多远才是高效率的? i i i k k a b a a b c k i i
k是追求的新起点 请抓住部分匹配时的两个特征: (1) s= a bea bc ac b a b’设目前打算与T的第字符开始比较 T=‘ a bca c 则T的k-1~0=S前i-1~i-k)位 (2 S= a b ab clabcac a b’刚才肯定是在S的处和的第字符处失配 T=abc(a 则T的j1~j-k位=S前i1~i-k)位 k T-k…T1截取一段,但有限制,0<kj 两式联立可得:T0…T=Tk…Tr 注意:j为当前己知的失配位置,我们的目标是计算新起点k 式中仅剩一个未知数k理论上已可解! 奇妙的结果:k仅与模式串I有关!
奇妙的结果： k 仅与模式串T有关！ 6 请抓住部分匹配时的两个特征： 两式联立可得：“T0…Tk-1”=‘Tj-k …Tj-1 ’ S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ i k 则T的k-1～０＝S前i-1～i-k)位 设目前打算与T的第k字符开始比较 (1) (2) ‘T０ …Tk-1 ’ 则T的j-1～j-k位＝ S前i-1～i-k)位 i k j S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ 刚才肯定是在S的i处和T的第j字符处失配 ‘Tj-k …Tj-1 ’ 截取一段，但k有限制，0<k<j k是追求的新起点 注意：j 为当前已知的失配位置，我们的目标是计算新起点 k。 式中仅剩一个未知数k，理论上已可解！
新起点k怎么求? 根据模式串T的规律 66 由当前失配位置(已知),可以归纳计算新起点k的表达式。 令k= next j](k与显然具有函数关系),则 当j=0时 nexj1=1max{k|0k且T…T=T-k…Tn,} 0其他情况 注意: 取T首与叮处最大的相同子串 (1)k值仅取决于模式串本身而与相匹配的主串无关。 (2)k值为模式串从头向后及从j向前的两部分的最大相同子串 的长度。 (3)这里的两部分子串可以有部分重叠的字符,但不可以全部 重叠
7 根据模式串T的规律： “T0…Tk-1”=“Tj-k …Tj-1 ” 由当前失配位置j(已知) ，可以归纳计算新起点 k的表达式。 next[ j ]＝ -1 当j＝0时 max { k | 0<k<j 且‘T0…Tk-1 ’=‘Tj-k …Tj-1 ’ } 0 其他情况 注意： （1）k值仅取决于模式串本身而与相匹配的主串无关。 （2）k值为模式串从头向后及从j向前的两部分的最大相同子串 的长度。 （3）这里的两部分子串可以有部分重叠的字符，但不可以全部 重叠。 令k = next[ j ]（k 与j 显然具有函数关系），则 取T首与Tj处最大的相同子串 新起点 k怎么求？
next[]函数表征着模式T中最大相同前缀子串和后缀子串 (真子串)的长度 可见,模式中相似部分越多,则 next[函数越大,它既 表示模式T字符之间的相关度越高,也表示位置以前与主串部 分匹配的字符数越多。 即: next[越大,模式串向右滑动得越远,与主串进行 比较的次数越少,时间复杂度就越低(时间效率)。 再想一想:如果主串是外存中一个 大文件,用KMP算法效果又如何?
8 next[ j]函数表征着模式T中最大相同前缀子串和后缀子串 （真子串）的长度。 可见，模式中相似部分越多，则next[ j]函数越大，它既 表示模式T字符之间的相关度越高，也表示j位置以前与主串部 分匹配的字符数越多。 即：next[ j]越大，模式串向右滑动得越远，与主串进行 比较的次数越少，时间复杂度就越低（时间效率）。 再想一想：如果主串是外存中一个 大文件，用KMP算法效果又如何？
怎样计算模式T所有可能的失配点j所对应的next[j? 例:模式串T: a b acac 可能失配位j:01234567 next[I与s无关 可以预先计算 新匹配位k= nextli]:-10011201 0当j=1时 刚才已归纳:mexj={max{kk且Tr…Tk=T+1)…T1} 讨论 1其他情况 j=0时, next[jI=-1;∥属于“=1”情况; j=1时, nextj=0;∥找不到0<k<j的k,属于“其他情况 j=2时, next j=0;/只需查看T’=‘T1成立否 3时,next1:/要查看T=4T2及TT1=T1T2是否 成立 j=4时,nex=1;/要查看"T0’=T3’,"ToT1’=T2T3和 以此类推,可得后续next值 是香成立 从两头往中间比较
9 从两头往中间比较 例： 模 式 串 T： a b a a b c a c 可能失配位j： 0 1 2 3 4 5 6 7 新匹配位k=next[j]: next[ j ]＝ 0 当j＝1时 max { k |1<k<j 且‘T1…Tk-1 ’=‘Tj-(k-1) …Tj-1 ’ } 1 其他情况 -1 0 0 1 1 2 0 1 讨论： j=0时, next[ j ]≡ -1；//属于“j=1”情况; j=1时, next[ j ]≡ 0；// 找不到0<k<j的k，属于“其他情况”； j=2时, next[ j ]≡ 0；//只需查看‘T0 ’=‘T1 ’成立否 j=3时, next[ j ]≡ 1；//要查看‘T0 ’=‘T2 ’ 及‘T0T1 ’=‘T1T2 ’ 是否 成立 j=4时, next[ j ]≡ 1；//要查看‘T0 ’=‘T3 ’ ，‘T0T1 ’=‘T2T3 ’ 和 ‘T0T1T2 ’=‘T1T2T3 ’是否成立 刚才已归纳： 以此类推，可得后续next[j]值。 next[ j]与s无关， 可以预先计算 怎样计算模式T所有可能的失配点 j 所对应的 next[j]？
下一个要讨论的问题是:如何用递推方式来求出最大相 同子串的长度呢?这个问题一旦解决,整个KMP算法就可以 掌握得很透彻了。 求子串next[i]值的算法: void GetNext(String T, int next[] I int j=0,k=0 next[0]=-1 while< t length)i if (t. strlj]==T. strLk]) next[j+1]-=k+1;j++;k++; else if (k==0)( next Lj+1=0; j++ J else k=next k]
10 下一个要讨论的问题是：如何用递推方式来求出最大相 同子串的长度呢？这个问题一旦解决，整个KMP算法就可以 掌握得很透彻了。 求子串next[i]值的算法： void GetNext(String T, int next[]) { int j = 0, k = 0; next[0] = -1; while(j < T.length){ if(T.str[j]==T.str[k]) { next[j+1]=k+1; j++; k++; } else if (k==0){ next[j+1]=0; j++; } else k=next[k]; } }