算法与数据结构3(字符串)

1、THU SAGroup课程编号：课程编号：741001521算法与数据结构（算法与数据结构（3 3）字符串）字符串赵俊峰赵俊峰 宁夏大学数学计算机学院计算机科学与技术专业2第三章第三章 字符串字符串v字符串及其运算字符串及其运算v字符串的存储表示字符串的存储表示v模式匹配模式匹配v本章小结本章小结3字符串的基本概念（字符串的基本概念（1 1）4字符串的基本概念（字符串的基本概念（2 2）5字符串的基本概念（字符串的基本概念（3 3）6字符串的基本运算字符串的基本运算7C C语言的字符串函数语言的字符串函数8第三章第三章 字符串字符串v字符串及其运算字符串及其运算v字符串的存储表示字符串的存储表

2、示v模式匹配模式匹配v本章小结本章小结9字符串的顺序存储字符串的顺序存储10字符串的链接存储字符串的链接存储11字符串块的链式存储字符串块的链式存储12第三章第三章 字符串字符串v字符串及其运算字符串及其运算v字符串的存储表示字符串的存储表示v模式匹配模式匹配v本章小结本章小结13模式匹配的问题定义模式匹配的问题定义14匹配思想匹配思想15匹配示例匹配示例16ExampleExample17匹配算法示意匹配算法示意18匹配算法匹配算法19算法时间效率分析算法时间效率分析20无回溯的模式匹配无回溯的模式匹配第一趟匹配第二趟匹配第三趟匹配a b a b c a b c a c b a ba b a

3、 b c a b c a c b a ba b a b c a b c a c b a ba b c a ca b c a c(a)b c a c21无回溯的模式匹配无回溯的模式匹配t0t1 tj-itj-i+1 tj-1 tjp0 p1 pk-1pkpi-1pi应滑动的位置：t0t1tj-itj-i+1tj-1 tj p0 p1pk-1pkpi-1pi 失配时的位置：p0p1pi-1 = tj-itj-i+1tj-1pi-kpi-k+1pi-1 = tj-itj-i+1tj-1设主串为 “t1t2tn”，模式串为“p1p2pm”假设此时tj应与模式串的第k（ki）个字符比较22无回溯的模式匹

4、配无回溯的模式匹配23NextNext数组的计算数组的计算当i=0时其他情况 i 0 1 2 3 4 5 6 7 模式串 a b a a b c a cnexti -1 0 0 1 1 2 0 1=-=-0 .0|1110ikikppppikkMaxinext且前后缀前后缀最大相最大相同字母同字母个数个数24无回溯的模式匹配无回溯的模式匹配 j=1第一趟匹配：第一趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b a a b c i=1 next1=0 j=1第二趟匹配：第二趟匹配： 主串主串 a c a b a a b a a b c

5、 a c a a b c 模式串模式串 a b a a b c i=0 next0=-1 j=2 j=7第三趟匹配：第三趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 a b a a b c i=0 i=5 next5=2 j=7 j=11第四趟匹配：第四趟匹配： 主串主串 a c a b a a b a a b c a c a a b c 模式串模式串 (a b) a a b c i=2 i=6 i0 1 2 3 4 5 模式串模式串a b a a b cnexti-1 0 0 1 1 225无回溯的模式匹配无回溯的模式匹配v t taabcbabcaabcaababcaabcbabcaabcaababcn n1818，v p p“abcaababcabcaababc”, , m m9 9。26无回溯的模式匹配