串类型的定义串的表示和实现串的模式匹配算法串操

1、1 物料管理STRG1Programing and Data Structures: String1、串类型的定义、串类型的定义2、串的表示和实现、串的表示和实现3、串的模式匹配算法、串的模式匹配算法4、串操作应用举例、串操作应用举例目录目录第第四四章章 串串2 物料管理STRG2Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法1、串的定长顺序存储表示、串的定长顺序存储表示define MAXSTRLEN 255 / 最大串长最大串长Typedef unsignedchar Sstring MAXSTRLEN + 1 ； / 可

2、用可用 0 号单元存放串长度号单元存放串长度模式模式 P（样品、子串）：要寻找的字符串，样品、子串）：要寻找的字符串， 存于存于T1 至至 T M之中；之中；主串：在其中寻找模式的主字符串，主串：在其中寻找模式的主字符串， 存于存于S1 至至 S N之中；之中；问题：在主串中寻找一个模式？如何做，更快？问题：在主串中寻找一个模式？如何做，更快？ 采用最笨的办法，一旦发现出现字符不匹配，则整个模式相对于原来的位置右移一位。采用最笨的办法，一旦发现出现字符不匹配，则整个模式相对于原来的位置右移一位。 如下图所示：如下图所示：Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1

3、 Pj 失配位置失配位置 P1 P2 Pj-1 Pj 下次匹配位置下次匹配位置e.g: S=a b c a b c a b c d P= a b c a b c d a b c a b c d 模式右移一位模式右移一位3 物料管理STRG3Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法2、最原始的模式匹配程序：、最原始的模式匹配程序：Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1 Pj 失配位置失配位置 P1 P2 Pj-1 Pj 下次匹配位置下次匹配位置int Index( SString S,

4、SString T, int pos ) / 在主串S的第POS个字符之后，寻找模式T的匹配位置 i = pos ; j = 1; while ( i = S0 & j T0 ) return i-T0 / T在S中的匹配起始位置 else return 0; / Index4 物料管理STRG4Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法）起因：降低时间代价，从最坏情况下的起因：降低时间代价，从最坏情况下的 O（ n * m）降

5、低到降低到 O（n +m）；）； 此处此处 n 是主串的字符个数、是主串的字符个数、m 是子串的字符个数。是子串的字符个数。历史：历史：70 年年S.A.cook 从理论上证明可在从理论上证明可在 O（n +m）内完成，以后由以内完成，以后由以 上三人给出实现的程序。上三人给出实现的程序。E.g：说明最坏情况下时间复杂性的说明最坏情况下时间复杂性的 O（ n * m）的实例。的实例。 每比较每比较m = 3 次，移动模式一次。最后在主串的次，移动模式一次。最后在主串的 n-m+1 找到主串，比较找到主串，比较 （n-m+1）* m 次次 S=aaaaaaaaab P=aab a、b不等不等模模

6、式右移一位式右移一位 S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位 S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位 S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位 S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab S=aaaaaaaaab P= aab a、b不等不等模模式右移一位式右移一位a、b不等不等模模式右移一位式右移一位a、b不等不等模模式右移一位式右移一位 完全匹配 n-m+1匹配起始位置匹配起始位置5 物料管理STR

7、G5Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 说明说明 KMP 算法的实例：算法的实例：e.g: S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd S = abcabcabcd P = abcabcd 失配点失配点右移一位，仍失配右移一位，仍失配又右移一位，仍失配又右移一位，仍失配再右移一位，三次比较之再右移一位，三次比较

8、之后，再进行断点处的比较后，再进行断点处的比较，比较上了！，比较上了！问题问题: 能否省去上述五次比较，直接能否省去上述五次比较，直接 进行进行 S7 和和 P4 之间的比较呢？之间的比较呢？本次比较省去！本次比较省去！本次比较省去！本次比较省去！三次比较省去！三次比较省去！6 物料管理STRG6Programing and Data Structures: Stringij3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 说明说明 KMP 算法的实例：算法的实例：e.g: S = abcabcabcd P = a

9、bcabcd S = abcabcabcd P = abcabcd 失配点失配点省去上述五次比较，直接进行省去上述五次比较，直接进行 Si 和和 Pj (即即S7同同P4)之间的比较的可能性。之间的比较的可能性。直接寻找新的匹配位置ij Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1 Pj 失配点失配点 分析：当分析：当 Si 和和 Pj 发生失配时，发生失配时， Si-j+1 Si-j+2 Si-1 P1 P2 Pj-1 Si-j+1 Si-k+1 Si-1 Si Si+1 P1 Pk-1 Pk 失配点失配点如果：如果： P1P2Pk-1 = Pj-k+1 Pj-

10、k+2 Pj-1；可以直接比较可以直接比较 前缀（长度前缀（长度k-1）= 以失配点的前一字符为结束位置的一串字符以失配点的前一字符为结束位置的一串字符7 物料管理STRG7Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 分析：多个前缀时，会出现什么问题呢？分析：多个前缀时，会出现什么问题呢？ e.g：S = aaaaabaab P = aaaabij前缀：前缀：P1P2P3P4 = aaaa P1P2P3 = aaa P1P2 = aa

11、 P1 = a 1、如果，取前缀长度、如果，取前缀长度 k-1 = j -1 ( 4 )，则则 Si = Pk 即即 Pj 进行比较，白做。故进行比较，白做。故 前缀长度前缀长度 不可以为不可以为 j - 1 。 2、如果，取前缀长度、如果，取前缀长度 k-1 = 1 或或 2 ，即前缀分别为，即前缀分别为 P1=a 或或 P1P2=aa 则正确的位置则正确的位置 会漏过去，不行。故：前缀长度太短也不行。会漏过去，不行。故：前缀长度太短也不行。jS = aaaaabaabP = aaaabijiS = aaaaabaabP = aaaab 3、因此应选前缀长度、因此应选前缀长度 k -1 j-

12、1 （此例为此例为 k - 1 = 3）的最长的前缀。的最长的前缀。8 物料管理STRG8Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） NEXTj 的定义：当失配点发生在的定义：当失配点发生在 Pj 处时，主串中的失配点将和模式中的哪一个字符进处时，主串中的失配点将和模式中的哪一个字符进 行比较。那一个字符的位置定义为行比较。那一个字符的位置定义为 NEXTj。ij=1S = abcabaP = abai0 如果如果 j =1 ，意味着

13、失配点意味着失配点 Si != P1， 下一次下一次 Si+1 =?= P1MAX k 1 k j 且且 P1 Pk-1 = Pj-k+1Pj-1 1NEXTj = 解释；解释；1、 j=1iS = abcabaP = aba 解释；解释；2、 k -1 = 1 ，所以所以: 1 k j Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2Pj-k+1 Pj-1 Pj P1 Pk-1Pk 解释；解释；3、 否则否则 Si =?= P1S = abcabaP = abaij=1iS = abcabaP = abaj=19 物料管理STRG9Programing and Data St

14、ructures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 求求 NEXTj 的实例：的实例：0 如果如果 j =1 ，意味着失配点意味着失配点 Si != P1， 下一次下一次 Si+1 =?= P1MAX k 1 k j 且且 P1 Pk-1 = Pj-k+1Pj-1 1NEXTj = Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2Pj-k+1 Pj-1 Pj P1 Pk-1Pk 求求 NEXTj ： e.g: j =1234567j = 12345678j = 1234

15、567 abcabcd abaabcac aaaaaaa NEXTj= 0111234 01122312 0123456 NEXTVALj= 0110114 01021302 000000010 物料管理STRG10Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法Si-j+1 Si-j+2 Si-1 Si Si+1 P1 P2 Pj-1 Pj P1 Pk int Index_KMP( SString S, SString T, int pos ) / 在主串S的第POS个字符之后，寻找模式T的匹配位置 / 已知 NEXT 函数值

16、，T 非空，1=pos=Strlength(S) i = pos ; j = 1; while ( i = S0 & j T0 ) return i-T0 / T在S中的匹配起始位置 else return 0; / Index_KMP3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） 利用利用 NEXTj 函数值寻找模式的程序函数值寻找模式的程序：11 物料管理STRG11Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式

17、匹配算法（KMP 算法）算法） NEXTj 函数值的求法函数值的求法：1、由定义，、由定义，next1 = 02、若若nexti = j ，求求 nexti+1 = ? 由已知可得：由已知可得： P1P2 Pj-1= Pi-j+1Pi-j+2Pi-1 、若若 Pj = Pi ；则则 P1P2 Pj-1 Pj=Pi-j+1Pi-j+2Pi-1 Pi 所以，所以， nexti+1 = j +1 、若若 Pj != Pi ；不得认为不得认为 nexti+1 = 1 ；参见下述例子：参见下述例子： P=abcabdabcabcwabcabdabcabdx 6 12?nexti=12且且ii+1 求求

18、nexti+1 虽然虽然 P12 != Pj ，但但P1P2 P5= Pj-5Pj-4Pj-1 推出：推出： P1P2 P5P6= Pi-5Pi-4Pi-1 Pi 由此可以推出：由此可以推出： nexti+1=7Void get_next ( SString T, int & next ) i =1 ; next1 = 0 ; j= 0 ; while ( i T0 ) if ( j = 0 Ti = Tj ) +i ; +j ; nexti = j; else j = next j ; / get_next P=abcabdabcabcwabcabdabcabdx i=1i i+1

19、注意：注意：i 是模式的指针。指针是模式的指针。指针 j 为前缀个数为前缀个数 + 112 物料管理STRG12Programing and Data Structures: String3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） KMP 算法的时间复杂性：算法的时间复杂性：O（n+m）n:主串长度，主串长度，m:模式长度模式长度。考察例子：考察例子： Sabcabcabcdabcdef Pabcabd1、从从 S 的指针观察，的指针观察， Ii 每右移一次，对应一次比较。因每右移一次，对应一次比较。因 此，

20、最多对应着此，最多对应着 n 次比较。次比较。2、从模式、从模式 P 进行考察，当失配时，进行考察，当失配时，j = nextj。主串失配主串失配 点点 Si 又将和又将和 Pj 进行比较，对应着新增加的比较次数。进行比较，对应着新增加的比较次数。 P 相对原来的位置右移。右移位数最多相对原来的位置右移。右移位数最多 n 次，新增加的次，新增加的 比较次数最多为比较次数最多为 n 次。次。所以，最多的比较次数最多为所以，最多的比较次数最多为 2n 次，同理生成次，同理生成 next 函函 数值的代价也不会大于数值的代价也不会大于 2m 。所以，总的代价所以，总的代价2(n+m)i13 物料管理

21、STRG13Programing and Data Structures: Stringii3、串的模式匹配算法、串的模式匹配算法3、Knuth-Morris-Pratt 模式匹配算法（模式匹配算法（KMP 算法）算法） KMP 算法的不用回溯的优点：算法的不用回溯的优点：考察例子：考察例子：Sabcabcabcdabcabd Pabcabd回溯：回溯：SabcabcabcdabcabdP abcabdi不回溯：不回溯：SabcabcabcdabcabdP abcabd12存放模式以存放模式以及模式的及模式的 next 值值存放主串的存放主串的每个扇区，每个扇区，一次存放一次存放 256 个字节个字节内存内存资料存于盘上资料存于盘上每个扇区每个扇区 256 个个字节字节模式模式 257 个字节个字节模式的前模式的前256 个个字节匹配