数据结构与算法1~4章.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 串模式匹配 串模式匹配 下面分析此算法的时间复杂度。显然，此算法的主要工作是do循环，它的循环次数与目标串及模式串相关，所以时间复杂度是个随机量。最理想的情况是，第一趟就得到匹配，此时的循环次数为n（即子串s的长度），而最坏的情况是不存在匹配，且每趟匹配过程都在比较完子串s中最后一个字符时才发现不能匹配，此种情况的循环次数是(m–n+1)×n，这里m为主串的长度。显然，n越大，此式的值越小。当n＜＜ m时，此式约等于m×n。 串模式匹配 无回溯的匹配算法 在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹配相当于将子串P后移1位再从头与主串中对应字符进行比较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配的起点的下一个位置，这样，主串中每个字符都要与子串中的第1个字符对应一次，再向后比较。因此，主串中每个字符参加比较的次数最多可达n次（n为子串长度），因此时间复杂度为O(nm)。那么，能否使目标串中每个字符只参加一次比较呢？也就是说，能否不回溯i指示器？回答是肯定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时解决的，所以有的文献也称这种思想的串匹配算法为KMP算法。 串模式匹配 i指示器之所以可不回溯，是因为重新开始一趟匹配时，可利用上趟匹配的结果。一般而言，一个无回溯匹配法的关键问题是，在匹配过程中一旦发现pj与ti不等，应能确定出从P中的哪个字符起与ti（或ti+1）对齐继续往下比较。这里记这个字符为pk，显然k＜j，且对不同的i，k也不同。Knoth等人发现这个k值仅仅依赖于子串P的前i个字符的构成，而与主串T无关。这是个令人鼓舞的发现，它是实现无回溯的关键。可用一个函数next表示j与k的这种对应关系，它是仅与子串有关的函数，其含义是，在匹配过程中，一旦发现一对不等的字符（设为pj与ti），若next(j)=k（k≥0），则下次的比较应从P中的pk起与T中的ti对齐往下进行；若next(j)＜0，则P中任何字符不必再与ti进行比较，下次比较从P的首字符起与ti+1对齐往下进行。next(j)的取值，应首先保证使匹配过程无遗漏（即不放过任何可能的匹配），其次，应使P串向后滑动尽可能长的距离。函数next( )称为失败函数。 串模式匹配 下面假定对给定的子串，它的next函数已确立，则串模式匹配算法可描述为以下程序的形式，它也是KMP算法的基本部分。 串模式匹配 以上程序中，用一维数组next[ ]表示失败函数next()，变量i只增不减，其初值为0，在循环中一直保持i＜n，所以i加1的语句i++至多执行n次，又因为next[j]＜j，且l≤j≤m，故语句j=next[j]至多执行m次，由于循环中只存在分别含有i++与j=next[j]的两个互斥分支，故循环次数不超过MAX(m, n)，因此算法的时间复杂度为O(MAX(m, n))。通常m＜n，故时间复杂度为O(n)。 串的应用——文本编辑 在办公室自动化、企业的现代化管理等许多领域中，文本编辑（程序）正发挥着越来越大的作用。文本编辑的实质是修改字符数据的形式或格式，如Microsoft Word，汉字信息处理系统（激光排版系统）等。虽然这些系统的功能不太一样，但基本操作一般都包括串的查找、插入和删除等操作，主要用于源程序的输入和修改，报刊和书籍的编辑排版及公文书信的起草与润色等。通常，整个文本可看成是一个字符串，其中，页是文本的子串，行又是页的子串。例如，以下程序便可看成是一个文本串： 串的应用——文本编辑 在该程序的输入过程中，由文本编辑程序为文本串建立相应的页表和行表，即建立各子串的存储映射。页表的每一项给出了页号和该页的起始行号，而行表的每一项则指示每一行的行号、起始地址和该行子串的长度。每输入的一行都可作为一个新的字符串加到文本中，串的值放在文本区中，行号、串值的存储地址及串长度则登记到表中。通过这个行表，新的一行可放到文本工作区的任何一个自由区中。设下图所示的文本串只占一页，且起始行号为200，则该文本串的行表如图所示。 串的应用——文本编辑 串的应用——文本编辑 下面讨论3种文本编辑的操作。 （1）插入。把新插入的