字符串与模式匹配算法.ppt

字符串与模式匹配算法用数组来实现链表结构作业讲评：链表应用举例——Josephus问题顺序表应用举例——Josephus问题算法复杂度分析（顺序结构）算法复杂度分析（链表结构）链表的用用：一元多项式和运算一元多项式表示和运算-3两个一元多项式的乘法字符串与模式匹配：C语言中定义的字符串串匹配函数：char*strstr(constchar[],constchar[]);线性表到字符串ADT顺序结构字符串ADT的定义顺序串示例字符串ADT——创建顺序结构空串链接结构字符串ADT的定义字符串的链接存储示例链接存储字符串的基本运算创建带头结点的空链串串模式匹配问题两种模式匹配方法朴素的模式匹配思想朴素的模式匹配——匹配子串朴素子串匹配法示例（每次p右移一个单元）35算法时间效率分析无回溯的模式匹配方法(KMP算法)模式串的特征数与特征向量KMP算法基本思想Next数组（特征向量）的计算然后把p右移若干位，tj以前的比较工作相当于用p0…pi-1的一个前缀与它的一个长度相同的后缀进行比较，显然比较的结果由p本身决定。