第三节串的匹配算法-深圳大学计算机与软件学院.ppt

第四章串 一、字符串（string） 字符串是n(≥0)个字符的有限序列，记作： S = ‘a1a2a3…an’ 其中，S 是串名字 ‘a1a2a3…an’是串值 ai 是串中字符 n 是串的长度(串中字符的个数) 例如, S = “Shenzhen University” 二、字符串术语 空串：不含任何字符的串，串长度=0 空格串：仅由一个或多个空格组成的串 子串：由串中任意个连续的字符组成的子序列。 主串：包含子串的串。 如：A=’Shenzhen University’ B=’University’ A为主串，B为子串。 二、字符串术语 位置：字符在序列中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。 串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。 模式匹配：确定子串在主串中首次出现的位置的运算 三、字符串与线性表的关系 串的逻辑结构和线性表极为相似，它们都是线性结构 串中的每个字符都仅有一个前驱和一个后继 三、字符串与线性表的关系 　串与线性表又有区别，主要表现为： 串的数据对象约定是字符集 在线性表的基本操作中，以“单个元素”作为操作对象 在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、在串的某个位置上插入一个子串等。 一、定长顺序存储表示 用一组地址连续的存储单元存储字符序列 如C语言中的字符串定义(以“\0”为串结束标志) char Str[MAXSTRLEN+1]; 定义了长度为MAXSTRLEN字符存储空间 字符串长度可以是小于MAXSTRLEN的任何值（最长串长度有限制，多余部分将被截断） 二、堆分配存储表示 在程序执行过程中，动态分配（malloc）一组地址连续的存储单元存储字符序列 在C语言中，由malloc()和free()动态分配与回收的存储空间称为堆 堆分配存储结构的串既有顺序存储结构的特点，处理方便,操作中对串长又没有限制,更显灵活 三、链存储表示 采用链表方式存储串值 每个结点中，可以存放一个字符，也可以存放多个字符 一、求子串位置函数Index() 子串的定位操作通常称做串的模式匹配 算法（穷举法）： 从主串的指定位置开始，将主串与模式（要查找的子串）的第一个字符比较， 1.若相等，则继续逐个比较后续字符； 2.若不等，从主串的下一个字符起再重新和模式的字符比较 一、求子串位置函数Index() Int Index(Sstring S, Sstring T, int pos) { //S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构 i = pos; j = 1; // 从第一个位置开始比较 while (i=S[0] j=T[0]) { if (S[i] == T[j]) {++i; ++j;} // 继续比较后继字符 else {i = i – j + 2; j = 1;} // 指针后退重新开始匹配 } if (j T[0]) return i-T[0]; // 返回与模式第一字符相等 else return 0; // 匹配不成功 // 的字符在主串中的序号 } 一、求子串位置函数Index() 在最好的情况下，除比较成功的位置外，其余位置仅需比较一次（模式第一个字符），其时间复杂度为：O(n+m)(n，m分别为主串和模式的长度) 但在最坏的情况下，如模式为，主串为‘0000000000000000000000000000000001’,则每次模式的前7个0都要与主串逐一比较，因此，其时间复杂度为：O(n*m) 二、KMP算法 是index函数的一种改进,由D.E.Knuth(克努特)－J.H.Morris(莫里斯)－V.R.Pratt(普拉特)发现 当一趟匹配过程中出现字符比较不等(失配)时 1.不需回溯i指针 2.利用已经得到的“部分匹配”的结果 3.将模式向右“滑动”尽可能远的一段距离(next[j])后，继续进行比较 二、KMP算法(举例) 假设主串ababcabcacbab,模式abcac,改进算法的匹配过程如下 ↓i=3 第一趟匹配 a b a b c a b c a c b a b a b c ↑j=3 ↓i=3----7 第二趟匹配 a b a b c a b c a c b a b a b c a c ↑j=1 ↓i=7--10 第三趟匹配 a b a b c a b c a c b a b