串的模式匹配算法

1、1第第4 4章章 串（串（StringString）4.1 4.1 串类型的定义串类型的定义4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 串的模式匹配算法串的模式匹配算法2算法目的：算法目的：确定主串中所含子串第一次出现的位置确定主串中所含子串第一次出现的位置（定位定位） 4.3 4.3 串的模式匹配算法串的模式匹配算法 BF算法算法 （又称古典的、经典的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的） KMP算法算法算法种类：算法种类：带回溯，速度慢带回溯，速度慢避免回溯，匹配速度快，避免回溯，匹配速度快，是全课程的亮点之一是全课程的亮点之一定位问题称为串的模式匹配定位

2、问题称为串的模式匹配，典型函数为典型函数为3BFBF算法的实现算法的实现即编写即编写Index(S, T, pos)Index(S, T, pos)函数函数例例1 1： S S=ababcabcacbab，T T=abcac，pospos=1=1， 求：串求：串T T在串在串S S中第中第pospos个字符之后的位置。个字符之后的位置。 利用利用演示系统演示系统看看BFBF算法执行过程。算法执行过程。BFBF算法设计思想：算法设计思想： 将主串将主串S S的第的第pospos个字符和模式个字符和模式T T的第的第1 1个字符比较，个字符比较， 若若相等相等，继续逐个比较后续字符；，继续逐个比较

3、后续字符； 若若不等不等，从主串从主串S S的下一字符（的下一字符（pos+1pos+1）起，）起，重新与重新与T T第一第一个字符比较。个字符比较。 直到主串直到主串S S的一个连续子串字符序列与模式的一个连续子串字符序列与模式T T相等。返回值相等。返回值为为S S中与中与T T匹配的子序列第一个字符的序号，即匹配成功。匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 .0 .4讨论：讨论：若若n n为主串长度，为主串长度，m m为子串长度，则串的为子串长度，则串的BFBF匹配算法最坏的情匹配算法最坏的情况下需要比较字符的总次数为况下需要比较字符的

4、总次数为(n-m+1)*mO(n*m)一般的情况是：一般的情况是：O(n+m) 推导方法：推导方法：BFBF算法的时间复杂度算法的时间复杂度最好的情况是：最好的情况是：一配就中！一配就中！ 只比较了只比较了m m次。次。能否加快子串（又称模式串）的滑动速度？能否加快子串（又称模式串）的滑动速度？能！利用已部分匹配过的信息使主串能！利用已部分匹配过的信息使主串S S的指针的指针i i不必回溯，最不必回溯，最坏情况也能达到坏情况也能达到O(n+m)O(n+m)最坏的情况是：最坏的情况是：主串前面主串前面n-mn-m个位置都个位置都部分匹配部分匹配到子串的最后一到子串的最后一位，即这位，即这n-mn

5、-m位比较了位比较了m m次，别忘了最后次，别忘了最后m m位也各比较了一次，还位也各比较了一次，还要加上要加上m m！所以总次数为：！所以总次数为：(n-m)*m+m (n-m+1)*m5KMPKMP算法算法（特点：速度快）（特点：速度快） KMPKMP算法设计思想算法设计思想 KMPKMP算法的推导过程算法的推导过程 KMPKMP算法的实现算法的实现 （关键技术（关键技术: :计算计算nextjnextj） KMPKMP算法的时间复杂度算法的时间复杂度6尽量利用已经尽量利用已经部分匹配部分匹配的结果信息，尽量让的结果信息，尽量让i i不要回溯，加快不要回溯，加快模式串的滑动速度。模式串的滑

6、动速度。例：例： KMP KMP算法设计思想：算法设计思想： ( (参见教材参见教材P80-84P80-84）S=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cS=a b a b c a b c a c b a bT=T=a b c a cIndex_kmpIndex_kmp的返回值应为的返回值应为i=6i=6需要讨论两个问题：需要讨论两个问题：如何由如何由当前部分匹配结果当前部分匹配结果确定模式向右滑动的新比较起点确定模式向右滑动的新比较起点k k？ 模式应该向右滑多远才是高效率的模

7、式应该向右滑多远才是高效率的? ?i ii ii ik kk k a b aa b ck ki ii ii-T0i-T07 KMP KMP算法的推导过程：算法的推导过程：（见教材（见教材P81P81）请抓住部分匹配时的两个特征：请抓住部分匹配时的两个特征：两式联立可得：两式联立可得：S=a b a b c a b c a c b a bT=T=a b c a ci ik k则则T T的的k-1k-11 1位位S S前前位位 即即(4-2(4-2）式含义）式含义设目前打算与设目前打算与T的第的第k字符开始比较字符开始比较(1)(1)(2)(2)则则T T的的j-1j-1j-(k-1)j-(k-1

8、)位位 S S前前位位 即即(4-3(4-3）式含义）式含义i ik kj jS=a b a b c a b c a c b a bT=T=a b c a c刚才肯定是在刚才肯定是在S的的i处和处和T的第的第j字符字符 处失配处失配加速的前提：加速的前提：T T首与首与TjTj处有相同子串处有相同子串注意：注意：j 为当前已知的失配位置，我们的目标是计算新起点为当前已知的失配位置，我们的目标是计算新起点 k。式中仅剩一个未知数式中仅剩一个未知数k，理论上已可解！，理论上已可解！8根据模式串根据模式串T的规律：的规律： 由当前失配位置由当前失配位置j(已知已知) ，可以，可以归纳归纳出计算新起点

9、出计算新起点 k的表达式。的表达式。next j 0 当当j1时时 /不比较不比较max k | 1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其他情况其他情况（1） next j 的物理意义是什么？的物理意义是什么？（2） next j 具体怎么求？具体怎么求？即即KMP算法的实现算法的实现令令k = next j （k 与与j 显然具有函数关系），则显然具有函数关系），则取取T T首与首与TjTj处最大的相同子串处最大的相同子串新起点新起点 k k怎么求？怎么求？9（1 1） next j next j 有何物理意义？有何物理意义？可见，模式中可见，模式中相似部分

10、越多，则相似部分越多，则nextjnextj函数越大函数越大，它既，它既表示表示模式模式T字符之间的相关度越高，也表示字符之间的相关度越高，也表示j j位置以前与主串位置以前与主串部部分匹配分匹配的字符数越多。的字符数越多。即：即：nextjnextj越大，模式串向右滑动得越远越大，模式串向右滑动得越远，与主串进行，与主串进行比较的次数越少，时间复杂度就越低（时间效率）。比较的次数越少，时间复杂度就越低（时间效率）。next j max k |1k1j1时，时，NextjNextj的值为：模式串的位置的值为：模式串的位置从从1 1到到j-1j-1构成的串中所出现的构成的串中所出现的首尾相同的子

11、串首尾相同的子串的最大长度的最大长度加加1 1。无首尾相同的子串时无首尾相同的子串时NextjNextj的值为的值为1 1。 / Nextj=1/ Nextj=1表示从模式串头部开始进行字符比较表示从模式串头部开始进行字符比较（2 2） next j next j 怎么计算？怎么计算？nextj11从两头往中间比较从两头往中间比较 模模 式式 串串 T： a b a a b c a c 可能失配位可能失配位 j： 1 2 3 4 5 6 7 8新匹配位新匹配位k=nextj :next j 0 当当j1时时max k |1kj 且且T1Tk-1=Tj-(k-1)j-(k-1) Tj-1 1 其

12、他情况其他情况0 1 1 2 2 3 1 2讨论：讨论：j=1时时, next j 0；/属于属于“j=1”情况情况;j=2时时, next j 1；/ 找不到找不到1kj的的k，属于，属于“其他情况其他情况”；刚才已归纳：刚才已归纳：j=3时时, k=2，只需查看，只需查看T1=T2 2成立否，成立否，No则属于其他情则属于其他情况况 j=4时时, k=2，3，要查看要查看T T1 1=T=T3 3 及及T T1 1T T2 2=T=T2 2 T T3 3 是否成立是否成立j=5时时, k=2，3，4，要查看，要查看T1=T4 4 ，T1T2=T3 3T4 和和 T1T2T3 3=T2 2T

13、3 3T4以此类推，可得后续以此类推，可得后续nextj值。值。可用演示程序验证可用演示程序验证nextjnextj与与s s无关，无关，可以预先计算可以预先计算例：例：12下一个要讨论的问题是：如何下一个要讨论的问题是：如何用递推方式用递推方式来求出最来求出最大相同子串的长度呢？换言之，如何让电脑替我们大相同子串的长度呢？换言之，如何让电脑替我们求出最大相同子串呢？这个问题一旦解决，整个求出最大相同子串呢？这个问题一旦解决，整个KMPKMP算法就可以掌握得很透彻了。算法就可以掌握得很透彻了。void get_next(SString T, int &next ) / /求模式串求模式

14、串T的的next函数值并存入数组函数值并存入数组next 。i=1; next1=0; j=0;while(iT0 ) if(j= = 0|Ti= =Tj)+i; +j; nexti=j;else j=nextj; / get_next递推法编程，参见教材递推法编程，参见教材P83P83程序程序13求解求解nextj流程图流程图（递推）（递推） i=1; j=0next1=0i1)f=n*fact(n-1); else f=1; return(f); 递推法：递推法：fact=1; for ( i=1; i=n; i+)fact*= i;例如：求例如：求f(n)=n!15第一步，先把模式第一步

15、，先把模式T所有可能的失配点所有可能的失配点j 所对应的所对应的nextj计算计算出来；出来；第二步：执行定位函数第二步：执行定位函数Index_kmp （与（与BFBF算法模块非常相似）算法模块非常相似） KMP KMP算法的实现算法的实现即即Index( )Index( )操作的实现操作的实现Int Index_KMP(SString S, SString T, int pos) /见教材见教材P82 i=pos; j=1; while ( i=S0 & jT0) return i-T0; /子串结束，说明匹配成功子串结束，说明匹配成功 else return0;/Index_KM

16、P/Index_KMP前面定义的前面定义的next函数在某些情况下还是有缺陷的，函数在某些情况下还是有缺陷的，例如模式例如模式aaaab与主串与主串aaabaaaab匹配时的情况：匹配时的情况：S: a a a b a a a a b T: a a a a b i: 1 2 3 4 5 6 7 8 9 a a a a ba a a a ba a a a b讨论：讨论： next j 是否完美无缺？是否完美无缺？先用演示程序验证先用演示程序验证似乎慢了一点？似乎慢了一点？能否再提速？能否再提速？由此派生出由此派生出next函数的改进算法函数的改进算法 T：a a a a bj：1 2 3 4 5 nextj： 0 1 2 3 4先计算先计算nextj：此时效率不高的原因为：子串前此时效率不高的原因为：子串前4 4位相同时，主串字符位相同时，主串字符若与其中一个不相等，则不必再与其余若与其中一个不相等，则不必再与其余3 3个比较。而实际个比较。而实际上还在依次比较。上还在依次比较。a a a a b17void get_nextval(SString T, int &nextval ) /next/next函数修正值存入数组函数修正值存入数组nextvalnextvali=1;