数据结构字符串.pptx

《数据结构字符串.pptx》由会员分享，可在线阅读，更多相关《数据结构字符串.pptx（86页珍藏版）》请在课桌文档上搜索。

1、字符串,字符串,字符串的范畴非常广泛；难题往往在此节出现；掌握字符串的法门是。字符串问题的晦涩代表：KMP、Manacher,主要内容,需要掌握的内容字符串循环左移LCS最长递增子序列字符串全排列递归、非递归KMPHuffman编码需要了解的内容Manacher算法BM算法,字符串循环左移,4/88,给定一个字符串S0N-1，要求把S的前k 个字符移动到S的尾部，如把字符串“abcdef”前面的2个字符a、b移动到字符串的尾 部，得到新字符串“cdefab”：即字符串循环 左移k。多说一句：循环左移k位等价于循环右移n-k位。算法要求：时间复杂度为 O(n)，空间复杂度为 O(1)。,问题分析

2、,5/88,暴力移位法每次循环左移1位，调用k次即可时间复杂度O(kN)，空间复杂度O(1)三次拷贝S0k T0kSk+1N-1 S0N-k-1T0k SN-kN-1时间复杂度O(N)，空间复杂度O(k),优雅一点的算法,6/88,(XY)=YX如：abcdefX=abX=baY=cdefY=fedc(XY)=(bafedc)=cdefab时间复杂度O(N)，空间复杂度O(1)该问题可以作为“完美洗牌”算法的子算法。,Code,7/88,LCS的定义,8/88,最长公共子序列，即Longest Common Subsequence，LCS。一个序列S任意删除若干个字符得到新序列T，则T 叫做S

3、的子序列；两个序列X和Y的公共子序列中，长度最长的那 个，定义为X和Y的最长公共子序列。字符串13455与245576的最长公共子序列为455字符串acdfg与adfc的最长公共子序列为adf注意区别最长公共子串(Longest Common Substring)最长公共字串要求连续,LCS的意义,9/88,求两个序列中最长的公共子序列算法，广泛的应用 在图形相似处理、媒体流的相似比较、计算生物学 方面。生物学家常常利用该算法进行基因序列比 对，由此推测序列的结构、功能和演化过程。LCS可以描述两段文字之间的“相似度”，即它们的 雷同程度，从而能够用来辨别抄袭。另一方面，对 一段文字进行修改之

4、后，计算改动前后文字的最长 公共子序列，将除此子序列外的部分提取出来，这 种方法判断修改的部分，往往十分准确。简而言 之，百度知道、百度百科都用得上。,暴力求解：穷举法,10/88,假定字符串X，Y的长度分别为m，n；X的一个子序列即下标序列1,2,m的严格递增 子序列，因此，X共有2m个不同子序列；同理，Y 有2n个不同子序列，从而穷举搜索法需要指数时间 O(2m.2n)；对X的每一个子序列，检查它是否也是Y的子序 列，从而确定它是否为X和Y的公共子序列，并且 在检查过程中选出最长的公共子序列；显然，不可取。,LCS的记号,11/88,字符串X，长度为m，从1开始数；字符串Y，长度为n，从1

5、开始数；Xi=x1，xi即X序列的前i个字符(1im)(Xi不妨读作“字符串X的i前缀”)Yj=y1，yj即Y序列的前j个字符(1jn)(字符串Y的j前缀)；LCS(X,Y)为字符串X和Y的最长公共子序列，即 为Z=z1，zk。注：不严格的表述。事实上，X和Y的可能存在多个子 串，长度相同并且最大，因此，LCS(X,Y)严格的说，是 个字符串集合。即：Z LCS(X,Y).,LCS解法的探索：xm=yn,12/88,若xm=yn(最后一个字符相同)，则：Xm与Yn 的最长公共子序列Zk的最后一个字符必定为 xm(=yn)。zk=xm=ynLCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm

6、,结尾字符相等，则LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm,记LCS(Xm,Yn)=W+xm，则W是Xm-1的子序列；同 理，W是Yn-1的子序列；因此，W是Xm-1和Yn-1的公 共子序列。反证：若W不是Xm-1和Yn-1的最长公共子序列，不妨记 LCS(Xm-1,Yn-1)=W，且|W|W|；那么，将W换成W，得到更长的LCS(Xm,Yn)=Wxm，与题设矛盾。,13/88,举例：xm=yn,14/88,对于上面的字符串X和Y：x3=y3=C，则：LCS(BDC,ABC)=LCS(BD,AB)+Cx5=y4=B，则：LCS(BDCAB,ABCB)=LCS(BDCA,ABC)

7、+B,LCS的探索：xmyn,若xmyn，则：要么：LCS(Xm,Yn)=LCS(Xm-1,Yn)要么：LCS(Xm,Yn)=LCS(Xm,Yn-1)证明：令Zk=LCS(Xm,Yn)；由于xmyn则zkxm与zkyn至少有 一个必然成立，不妨假定zkxm(zkyn的分析与之类似)因为zkxm，则最长公共子序列Zk是Xm-1和Yn得到的，即：Zk=LCS(Xm-1,Yn)同理，若zkyn，则Zk=LCS(Xm,Yn-1)即，若xmyn，则：LCS(Xm,Yn)=maxLCS(Xm-1,Yn),LCS(Xm,Yn-1),15/88,举例：xmyn,16/88,对于字符串X和Y：x2y2，则：LC

8、S(BD,AB)=max LCS(BD,A),LCS(B,AB)x4y5，则：LCS(BDCA,ABCBD)=max LCS(BDCA,ABCB),LCS(BDC,ABCBD),LCS分析总结,17/88,显然，属于动态规划问题。,mn,mn,当x y,当xm=yn,m1nmn1,maxLCS(X,Y),LCS(X,Y),LCS(Xm1,Yn1)+xm,LCS(X,Y)=,算法中的数据结构：长度数组,18/88,使用二维数组Cm,nci,j记录序列Xi和Yj的最长公共子序列的长 度。当i=0或j=0时，空序列是Xi和Yj的最长公共子序 列，故ci,j=0。,j,i,j,i,当i 0,j 0,且

9、x y,maxc(i 1,j),c(i,j 1),当i 0,j 0,且x=y,当i=0或者j=0,0,c(i,j)=c(i 1,j 1)+1,算法中的数据结构：方向变量,19/88,使用二维数据Bm,n，其中，bi,j标记ci,j 的值是由哪一个子问题的解达到的。即ci,j 是由ci-1,j-1+1或者ci-1,j或者ci,j-1的哪一 个得到的。取值范围为Left，Top，LeftTop 三种情况。,实例,X=Y=,20/88,Code,21/88,算法实现Demo,22/88,进一步思考的问题,23/88,方向数组b是完全可以省略的：数组元素ci,j的值仅由ci-1,j-1，ci-1,j和

10、ci,j-1 三个值之一确定，因此，在计算中，可以临时判 断ci,j的值是由ci-1,j-1，ci-1,j和ci,j-1中哪一 个数值元素所确定，代价是O(1)时间。若只计算LCS的长度，则空间复杂度为O(min(m,n)。在计算ci,j时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公 共子序列的长度。,最大公共子序列的多解性：求所有的LCS,当xmyn时：若LCS(Xm-1,Yn)=LCS(Xm,Yn-1)，会导致多解：有多个最长公共子序 列，并且它们的长度相等。B的取值范围从1,2,3扩展到1,2,3,4深度/广度优先搜索,mn,mn,当x y,当xm=y

11、n,m1nmn1,maxLCS(X,Y),LCS(X,Y),LCS(Xm1,Yn1)+xm,LCS(X,Y)=,24/88,LCS的应用：最长递增子序列LIS,25/88,Longest Increasing Subsequence给定一个长度为N的数组，找出一个最长的 单调递增子序列。例如：给定数组 5，6，7，1，2，8，则其最长的单调递增子序列为5，6，7，8，长度为4。分析：其实此LIS问题可以转换成最长公子序列 问题，为什么呢？,使用LCS解LIS问题,26/88,原数组为A 5，6，7，1，2，8排序后：A1，2，5，6，7，8因为，原数组A的子序列顺序保持不变，而且排序 后A本身

12、就是递增的，这样，就保证了两序列的最 长公共子序列的递增特性。如此，若想求数组A的 最长递增子序列，其实就是求数组A与它的排序数 组A的最长公共子序列。此外，本题也可以直接使用动态规划/贪心法来求解,附：LIS的动态规划解法,长度为N的数组记为A=a0a1a2.an-1；记A的前i个字符构成的前缀串为Ai=a0a1a2.ai-1，以ai结尾的最长递增子序列记做 Li，其长度记为bi；假定已经计算得到了b0,1,i-1，如何计算bi呢？已知L0 L1 Li-1的前提下，如何求Li？,27/88,附：求解LIS,根据定义，Li必须以ai结尾；如果将ai分别缀到L0 L1 Li-1后面，是否允许呢？

13、如果aiaj，则可以将ai缀到Lj的后面，得到比Lj更长 的字符串。从而：bi=max(bj)+1,0ji且ajai计算bi：遍历在i之前的所有位置j，找出满足条件ajai的最大的bj+1；计算得到b0n-1后，遍历所有的bi，找出最大值 即为最大递增子序列的长度。时间复杂度为O(N2)。,28/88,附：Code,29/88,附：Code split,30/88,字符串的全排列,31/88,给定字符串S0N-1，设计算法，枚举S的 全排列。,递归算法,32/88,以字符串1234为例：1 234 2 134 3 214 4 231如何保证不遗漏保证递归前1234的顺序不变,递归Code,33

14、/88,如果字符有重复,34/88,去除重复字符的递归算法以字符1223为例：1 2232 1233 221带重复字符的全排列就是每个字符分别与它后面非 重复出现的字符交换。即：第i个字符与第j个字符交换时，要求i,j)中没有 与第j个字符相等的数。,Code,35/88,重复字符的全排列递归算法时间复杂度,36/88,f(n)=n*f(n-1)+n2f(n-1)=(n-1)*f(n-2)+(n-1)2f(n)=n*(n-1)*f(n-2)+(n-1)2)+n2 f(n-2)=(n-2)*f(n-3)+(n-2)2 f(n)=n*(n-1)*(n-2)*f(n-3)+(n-2)2)+n*(n-

15、1)2+n2=n*(n-1)*(n-2)*f(n-3)+n*(n-1)*(n-2)2+n*(n-1)2+n2=.n+1,空间换时间,37/88,空间换时间的方法,38/88,如果是单字符，可以使用mark256；如果是整数，可以遍历整数得到最大值max 和最小值min，使用markmax-min+1；如果是浮点数或其他结构，考虑使用Hash。事实上，如果发现整数间变化太大，也应该考 虑使用Hash；可以认为整数/字符的情况是最朴素的Hash。,全排列的非递归算法,39/88,起点：字典序最小的排列，例如12345终点：字典序最大的排列，例如54321过程：从当前排列生成字典序刚好比它大的 下一

16、个排列 如：21543的下一个排列是23145如何计算？,21543的下一个排列的思考过程,40/88,逐位考察哪个能增大一个数右面有比它大的数存在，它就能增大那么最后一个能增大的数是x=11应该增大到多少？增大到它右面比它大的最小的数y=3应该变为23xxx显然，xxx应由小到大排：145 得到23145,全排列的非递归算法：整理成算法语言,41/88,步骤：后找、小大、交换、翻转后找：字符串中最后一个升序的位置i，即：SkSk+1(ki)，SiSi+1；查找(小大)：Si+1N-1中比Ai大的最小值Sj；交换：Si，Sj；翻转：Si+1N-1思考：交换操作后，Si+1N-1一定是降序的以9

17、26520为例，考察该算法的正确性。,非递归算法Code,42/88,几点说明,43/88,下一个排列算法能够天然的解决重复字符的 问题！不妨还是考察926520的下一个字符串C+STL已经在Algorithm中集成了 next_permutation可以将给定的字符串A0N-1首先升序排 序，然后依次调用next_permutation直到返回 false，即完成了非递归的全排列算法。,KMP算法,44/88,字符串查找问题给定文本串text和模式串pattern，从文本串text中找出模 式串pattern第一次出现的位置。最基本的字符串匹配算法暴力求解(Brute Force)：时间复杂

18、度O(m*n)KMP算法是一种线性时间复杂度的字符串匹配算 法，它是对BF算法改进。记：文本串长度为N，模式串长度为MBF算法的时间复杂度O(M*N)，空间复杂度O(1)KMP算法的时间复杂度O(M+N)，空间复杂度O(M),暴力求解,45/88,分析BF与KMP的区别,46/88,假设当前文本串text匹配到i位置，模式串pattern串 匹配到j位置。BF算法中，如果当前字符匹配成功，即texti+j=patternj，令i+，j+，继续匹配下一个字符；如果失配，即texti+jpatternj，令i+，j=0，即每次 匹配失败的情况下，模式串pattern相对于文本串text向右 移动了

19、一位。KMP算法中，如果当前字符匹配成功，即 texti+j=patternj，令i+，j+，继续匹配下一个 字符；如果失配，即texti+jpatternj，令i不变，j=nextj，(这里，nextjj-1)，即模式串pattern相对于文本串text 向右移动了至少1位(移动的实际位数j-nextj1),描述性说法,47/88,在暴力求解中，为什么模式串的索引会回 溯？因为模式串存在重复字符思考：如果模式串的字符两两不相等呢？可以方便快速的编写线性时间的代码更弱一些的条件：如果模式串的首字符和其他 字符不相等呢？,挖掘字符串比较的机制,48/88,分析后的结论,对于模式串的位置j，考察P

20、atternj-1=p0p1.pj-2pj-1，查找字符串Patternj-1的最大相等k前缀和k后缀。注：计算nextj时，考察的字符串是模式串的前j-1个字符，与patternj无关。即：查找满足条件的最大的k，使得p0p1.pk-2pk-1=pj-kpj-k+1.pj-2pj-1,49/88,求模式串的next,如：j=5时，考察字符 串“abaab”的最大相等 k前缀和k后缀,50/88,next的递推关系,对于模式串的位置j，有nextj=k，即：p0p1.pk-2pk-1=pj-kpj-k+1.pj-2pj-1则，对于模式串的位置j+1，考察pj：若pk=pjnextj+1=nex

21、tj+1若pkpj记h=nextk；如果ph=pj,则nextj+1=h+1，否则重复此过程。,51/88,考察不相等时，为何可以递归下去,若pkpj记h=nextk；如果ph=pj,则nextj+1=h+1，否则重复此过程,52/88,计算Next数组,53/88,KMP Code,54/88,进一步分析next,文本串匹配到i，模式串匹配到j，此刻，若textipatternj，即失配的情况：若nextj=k，说明模式串应该从j滑动到k位置；若此时满足patternj=patternk，因为textipatternj，所以，texti patternk即i和k没有匹配，应该继续滑动到nex

22、tk。换句话说：在原始的next数组中，若nextj=k并且patternj=patternk，nextj可以直接等于nextk。,55/88,Code2,56/88,求模式串的next变种,57/88,理解KMP的时间复杂度,58/88,我们考察模式串的“串头”和主串的对应位置(也就是 暴力算法中的i)。不匹配：串头后移，保证尽快结束算法；匹配：串头保持不动(仅仅是i+、j+，但串头和主 串的对应位置没变)，但一旦发现不匹配，会跳过 匹配过的字符(nextj)。最坏的情况，当串头位于N-M的位置，算法结束因此，匹配的时间复杂度为O(N)，算上计算next的O(M)时间，整体时间复杂度为O(M

23、+N)。,考察KMP的时间复杂度,59/88,最好情况：当模式串的首字符和其他字符都 不相等时，模式串不存在相等的k前缀和k后 缀，next数组全为-1一旦匹配失效，模式串直接跳过已经比较的字 符。比较次数为N最差情况：当模式串的首字符和其他字符全 都相等时，模式串存在最长的k前缀和k后 缀，next数组呈现递增样式：-1,0,1,2举例说明,KMP最差情况,next:-1 0 1 2 3 比较次数：5 1 1 1 1周期：n/5总次数：1.8n每个周期中:m 1 1 1周期：n/m,M,60/88,总次数：,2 1 N 2N,最差情况下，变种KMP的运行情况,next:-1-1-1-1-1比

24、较次数：5周期：n/5总次数：n,61/88,KMP的next，实际上是建立了DFA,以当前位置为DFA的状态，以模式串的字符 为DFA的转移条件，建立确定有穷自动机Deterministic Finite Automaton,图片来自网络,62/88,附：DFA和NFA,63/88,DFA的五要素非空有限的状态集合Q输入字母表转移函数开始状态S结束状态F对于一个给定的DFA，存在唯一一个对应的有向图；有向图的 每个结点对应一个状态，每条有向边对应一种转移。习惯上将 结点画成两个圈表示接受状态，一个圈表示拒绝状态。用一条 没有起点的边指向起始状态。如果从某个状态，在确定的输入条件下，状态转移是

25、多个状 态，则这样的自动机是非确定有穷自动机。可以证明，DFA和NFA是等价的，它们识别的语言成为正则语 言。,KMP应用：PowerString问题,64/88,给定一个长度为n的字符串S，如果存在一个 字符串T，重复若干次T能够得到S，那么，S叫做周期串，T叫做S的一个周期。如：字符串abababab是周期串，abab、ab都 是它的周期，其中，ab是它的最小周期。设计一个算法，计算S的最小周期。如果S不 存在周期，返回空串。,使用next，线性时间解决问题,65/88,计算S的next数组；记k=nextlen，p=len-k；若len%p=0，则p为最小周期长度，前p个字符就是最小周期

26、。说明：使用的是经典KMP的next算法，非变种KMP的next算法；要“多”计算到len，即nextlen。思考：如何证明？考察字符串S的k前缀first和k后缀tail：1、first和tail的前p个字符2、first和tail的前2*p个字符3、first和tail的前3*p个字符,求字符串周期,66/88,Code,67/88,思考题：字符串的最长回文子串,68/88,回文子串的定义：给定字符串str，若s同时满足以下条件：s是str的子串s是回文串则，s是str的回文子串。该算法的要求，是求str中最长的那个回文子 串。Manacher算法,重建Manacher,我们的任务：假定已

27、经得到了前i个值，考察i+1如何计算即：在P0.i-1已知的前提下，计算Pi的值。换句话说，算法 的核心，是在P0.i-1已知的前提下，能否给Pi的计算提供一 点有用的信息呢？1、通过简单的遍历，得到i个三元组k,Pk,k+Pk，0ki-1trick：以k为中心的字符形成的最大回文子串的最右位置是k+Pk-12、以k+Pk为关键字，挑选出这i个三元组中，k+Pk最大的那个 三元组，不妨记做(id,Pid，Pid+id)。进一步，为了简化，记 mx=Pid+id，因此，得到三元组为(id,Pid,mx)，这个三元组的含 义非常明显：所有i个三元组中，向右到达最远的位置，就是mx；3、在计算Pi的

28、时候，考察i是否落在了区间0,mx)中；若i在mx的右侧，说明0,mx)没有能够控制住i，P0.i-1的已 知，无法给Pi的计算带来有价值信息；若i在mx的左侧，说明0,mx)控制(也有可能部分控制)了i，现在 以图示来详细考察这种情况。,69/88,思考：BM算法,70/88,Boyer-Moore算法是1977年，德克萨斯大学 的Robert S.Boyer教授和J Strother Moore教授 发明的字符串匹配算法，拥有在最坏情况下 O(N)的时间复杂度，并且，在实践中，比 KMP算法的实际效能高。BM算法不仅效率高，而且构思巧妙，容易 理解。坏字符-好后缀,附：坏字符引起的模式滑动

29、,依然从尾部开始比较，发现P与E不匹 配，所以P是坏字符。但是，P包含在 搜索词EXAMPLE之中。所以，将搜索词 后移两位，两个P对齐。,71/88,附：考虑好后缀,72/88,面试题,73/88,用二进制来编码字符串“uarejulyapp”，需要 能够根据编码，解码回原来的字符串，最少 需要位的二进制字符串？仅修改了字符串本身。,二叉树的结点,74/88,令有2个孩子、1个孩子和0个孩子的结点个数分别 为n2、n1、n0所有结点的出度为2*n2+1*n1+0*n0除了根结点，其他所有结点的入度都是1，从而所 有结点的入度为(n2+n1+n0)-1；总入度等于总出度，2*n2+1*n1+0

30、*n0=n2+n1+n0-1化简得n0-n2=1二叉树叶子节点数目比两个孩子的结点数目多1。,Huffman编码,75/88,Huffman编码是一种无损压缩编码方案。思想：根据源字符出现的(估算)概率对字符 编码，概率高的字符使用较短的编码，概率 低的使用较长的编码，从而使得编码后的字 符串长度期望最小。Huffman编码是一种贪心算法：每次总选择 两个最小概率的字符结点合并。称字符出现的次数为频数，则概率约等于频数 除以字符总长；因此，概率可以用频数代替。,算法演示,76/88,Code,77/88,Code,78/88,Main Code,79/88,Aux Code,80/88,Aux

31、 Code,81/88,实验结果,82/88,Huffman编码总结：前缀编码,83/88,Huffman编码是不等长编码字符的编码长度不完全相同。不等长编码如果需要译码，必须满足“前缀编码”的 条件：任何一个字符的编码都不是另外一个字符编 码的前缀。字符串：ABBC使用编码方案：A:0B:1C:00则，ABBC的 编码为：0110001100的译码可以是ABBC，也可以是ABBAA。,Huffman实现带来的思考,Huffman编码是如何解决前缀编码问题的？实际算法往往是由多个“小算法”堆砌而成的。空格压缩问题取数组最大/小的两个数代码实现中并非直接使用指针形成的二叉树结点。而是事先开辟足够

32、大的缓冲空间(2n+1)，每次从缓 冲区获取一个结点，使用数组代替二叉树。在堆排序、双数组Trie树结构等问题中会再次遇到。最后，由于Huffman树的结点权值(频数)可能相 等，因此，对某些文本，Huffman编码不唯一。“左赋1，右赋0”或者“左赋0，右赋1”都可以。,字符串查找的思考,85/88,字符串和树相结合，往往会产生查找思路上 的变革，如Trie树、后缀树(后缀数组)；一个文本文件，大约有一百万行，每行一个 词，要求统计出其中最频繁出现的前10个词将在树、海量数据搜索等章节详细论述。海量数据的字符串查找，往往需要Hash表。在10亿个URL中，查找某URL的出现位置千万别回答：计算待查找字符串的next数组，用KMP算法。,字符串总结,86/88,字符串查找：增删改查KMP/BMmap/set：R-BTreeHashTrie树对字符串本身的操作全排列Manacher回文划分,