July_algorithm 2.字符串.pdf

《July_algorithm 2.字符串.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 2.字符串.pdf（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、字符串七月算法邹博2015年10月18日10月算法在线班2/字符串 字符串的范畴非常广泛；难题往往在此节出现；掌握字符串的法门是_。字符串问题的晦涩代表：KMP、Manacher10月算法在线班3/主要内容 需要掌握的内容字符串循环左移LCS最长递增子序列字符串全排列 递归、非递归KMPHuffman编码 需要了解的内容Manacher算法BM算法10月算法在线班4/字符串循环左移 给定一个字符串S0N-1，要求把S的前k个字符移动到S的尾部，如把字符串“abcdef”前面的2个字符a、b移动到字符串的尾部，得到新字符串“cdefab”：即字符串循环左移k。多说一句：循环左移k位等价于循环右移

2、n-k位。算法要求：时间复杂度为 O(n)，空间复杂度为 O(1)。10月算法在线班5/问题分析 暴力移位法 每次循环左移1位，调用k次即可 时间复杂度O(kN)，空间复杂度O(1)三次拷贝 S0k T0k Sk+1N-1 S0N-k-1 T0k SN-kN-1 时间复杂度O(N)，空间复杂度O(k)10月算法在线班6/优雅一点的算法(XY)=YX 如：abcdef X=ab X=ba Y=cdefY=fedc(XY)=(bafedc)=cdefab 时间复杂度O(N)，空间复杂度O(1)该问题可以作为“完美洗牌”算法的子算法。10月算法在线班7/Code10月算法在线班8/LCS的定义 最长

3、公共子序列，即Longest Common Subsequence，LCS。一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列；两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列。字符串13455与245576的最长公共子序列为455字符串acdfg与adfc的最长公共子序列为adf 注意区别最长公共子串(Longest Common Substring)最长公共字串要求连续10月算法在线班9/LCS的意义 求两个序列中最长的公共子序列算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、

4、功能和演化过程。LCS可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。10月算法在线班10/暴力求解：穷举法 假定字符串X，Y的长度分别为m，n；X的一个子序列即下标序列1,2,m的严格递增子序列，因此，X共有2m个不同子序列；同理，Y有2n个不同子序列，从而穷举搜索法需要指数时间O(2m.2n)；对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选

5、出最长的公共子序列；显然，不可取。10月算法在线班11/LCS的记号 字符串X，长度为m，从1开始数；字符串Y，长度为n，从1开始数；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).10月算法在线班12/LCS解法的探索：xm=yn 若xm=yn(最后一个字符相同)，则：Xm与Yn的最

6、长公共子序列Zk的最后一个字符必定为xm(=yn)。zk=xm=yn LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm10月算法在线班13/结尾字符相等，则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，与题设矛盾。10月算法在线班14/举例：xm=ynBADBCBAYABACDBX7654

7、321对于上面的字符串X和Y：x3=y3=C，则：LCS(BDC,ABC)=LCS(BD,AB)+Cx5=y4=B，则：LCS(BDCAB,ABCB)=LCS(BDCA,ABC)+B10月算法在线班15/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=LC

8、S(Xm,Yn-1)即，若xmyn，则：LCS(Xm,Yn)=maxLCS(Xm-1,Yn),LCS(Xm,Yn-1)10月算法在线班16/举例：xmynBADBCBAYABACDBX7654321对于字符串X和Y：x2y2，则：LCS(BD,AB)=max LCS(BD,A),LCS(B,AB)x4y5，则：LCS(BDCA,ABCBD)=max LCS(BDCA,ABCB),LCS(BDC,ABCBD)10月算法在线班17/LCS分析总结 显然，属于动态规划问题。nmnmnmnmmnmnmyxYXLCSYXLCSyxxYXLCSYXLCS当当1111,max,10月算法在线班18/算法中的

9、数据结构：长度数组 使用二维数组Cm,n ci,j记录序列Xi和Yj的最长公共子序列的长度。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故ci,j=0。jijiyxjijicjicyxjijicjijic且当且当或者当,0,01,1max,0,011,1000,10月算法在线班19/算法中的数据结构：方向变量 使用二维数据Bm,n，其中，bi,j标记ci,j的值是由哪一个子问题的解达到的。即ci,j是由ci-1,j-1+1或者ci-1,j或者ci,j-1的哪一个得到的。取值范围为Left，Top，LeftTop三种情况。10月算法在线班20/实例 X=Y=10月算法在线班21/Co

10、de10月算法在线班22/算法实现Demo10月算法在线班23/进一步思考的问题 方向数组b是完全可以省略的：数组元素ci,j的值仅由ci-1,j-1，ci-1,j和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行的数组空间就可以计算出最长公共子序列的长度。10月算法在线班24/最大公共子序列的多解性：求所有的LCS 当xmyn时：若LCS(Xm-1,Yn)=

11、LCS(Xm,Yn-1)，会导致多解：有多个最长公共子序列，并且它们的长度相等。B的取值范围从1,2,3扩展到1,2,3,4 深度/广度优先搜索nmnmnmnmmnmnmyxYXLCSYXLCSyxxYXLCSYXLCS当当1111,max,10月算法在线班25/LCS的应用：最长递增子序列LIS Longest Increasing Subsequence 给定一个长度为N的数组，找出一个最长的单调递增子序列。例如：给定数组 5，6，7，1，2，8，则其最长的单调递增子序列为5，6，7，8，长度为4。分析：其实此LIS问题可以转换成最长公子序列问题，为什么呢？10月算法在线班26/使用LCS

12、解LIS问题 原数组为A 5，6，7，1，2，8 排序后：A1，2，5，6，7，8 因为，原数组A的子序列顺序保持不变，而且排序后A本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。如此，若想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A的最长公共子序列。此外，本题也可以直接使用动态规划/贪心法来求解10月算法在线班27/附：LIS的动态规划解法 长度为N的数组记为A=a0a1a2.an-1；记A的前i个字符构成的前缀串为Ai=a0a1a2.ai-1，以ai结尾的最长递增子序列记做Li，其长度记为bi；假定已经计算得到了b0,1,i-1，如何计算bi呢？已知L0 L1

13、Li-1的前提下，如何求Li？10月算法在线班28/附：求解LIS 根据定义，Li必须以ai结尾；如果将ai分别缀到L0 L1Li-1后面，是否允许呢？如果aiaj，则可以将ai缀到Lj的后面，得到比Lj更长的字符串。从而：bi=max(bj)+1,0ji且ajai 计算bi：遍历在i之前的所有位置j，找出满足条件ajai的最大的bj+1；计算得到b0n-1后，遍历所有的bi，找出最大值即为最大递增子序列的长度。时间复杂度为O(N2)。10月算法在线班29/附：Code10月算法在线班30/附：Code split10月算法在线班31/字符串的全排列 给定字符串S0N-1，设计算法，枚举S的全

14、排列。10月算法在线班32/递归算法 以字符串1234为例：1 234 2 134 3 214 4 231 如何保证不遗漏 保证递归前1234的顺序不变10月算法在线班33/递归Code10月算法在线班34/如果字符有重复 去除重复字符的递归算法 以字符1223为例：1 223 2 123 3 221 带重复字符的全排列就是每个字符分别与它后面非重复出现的字符交换。即：第i个字符与第j个字符交换时，要求i,j)中没有与第j个字符相等的数。10月算法在线班35/Code10月算法在线班36/重复字符的全排列递归算法时间复杂度 f(n)=n*f(n-1)+n2 f(n-1)=(n-1)*f(n-2

15、)+(n-1)2 f(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-1)2+n2=n*(n-1)*(n-2)*f(n-3)+n*(n-1)*(n-2)2+n*(n-1)2+n2=.n+110月算法在线班37/空间换时间10月算法在线班38/空间换时间的方法 如果是单字符，可以使用mark256；如果是整数，可以遍历整数得到最大值max和最小值min，使用markmax-min+1；如果是浮点数或其他结构，考虑使用Hash。事实上，如果发现整数间变化太大

16、，也应该考虑使用Hash；可以认为整数/字符的情况是最朴素的Hash。10月算法在线班39/全排列的非递归算法 起点：字典序最小的排列，例如12345 终点：字典序最大的排列，例如54321 过程：从当前排列生成字典序刚好比它大的下一个排列 如：21543的下一个排列是23145 如何计算？10月算法在线班40/21543的下一个排列的思考过程 逐位考察哪个能增大 一个数右面有比它大的数存在，它就能增大 那么最后一个能增大的数是x=1 1应该增大到多少？增大到它右面比它大的最小的数y=3 应该变为23xxx 显然，xxx应由小到大排：145 得到2314510月算法在线班41/全排列的非递归算

17、法：整理成算法语言 步骤：后找、小大、交换、翻转 后找：字符串中最后一个升序的位置i，即：SkSk+1(ki)，SiSi+1；查找(小大)：Si+1N-1中比Ai大的最小值Sj；交换：Si，Sj；翻转：Si+1N-1思考：交换操作后，Si+1N-1一定是降序的 以926520为例，考察该算法的正确性。10月算法在线班42/非递归算法Code10月算法在线班43/几点说明 下一个排列算法能够天然的解决重复字符的问题！不妨还是考察926520的下一个字符串 C+STL已经在Algorithm中集成了next_permutation 可以将给定的字符串A0N-1首先升序排序，然后依次调用next_p

18、ermutation直到返回false，即完成了非递归的全排列算法。10月算法在线班44/KMP算法 字符串查找问题给定文本串text和模式串pattern，从文本串text中找出模式串pattern第一次出现的位置。最基本的字符串匹配算法暴力求解(Brute Force)：时间复杂度O(m*n)KMP算法是一种线性时间复杂度的字符串匹配算法，它是对BF算法改进。记：文本串长度为N，模式串长度为MBF算法的时间复杂度O(M*N)，空间复杂度O(1)KMP算法的时间复杂度O(M+N)，空间复杂度O(M)10月算法在线班45/暴力求解10月算法在线班46/分析BF与KMP的区别 假设当前文本串te

19、xt匹配到i位置，模式串pattern串匹配到j位置。BF算法中，如果当前字符匹配成功，即texti+j=patternj，令i+，j+，继续匹配下一个字符；如果失配，即texti+jpatternj，令i+，j=0，即每次匹配失败的情况下，模式串pattern相对于文本串text向右移动了一位。KMP算法中，如果当前字符匹配成功，即texti+j=patternj，令i+，j+，继续匹配下一个字符；如果失配，即texti+jpatternj，令i不变，j=nextj，(这里，nextjj-1)，即模式串pattern相对于文本串text向右移动了至少1位(移动的实际位数j-nextj1)10

20、月算法在线班47/描述性说法 在暴力求解中，为什么模式串的索引会回溯？因为模式串存在重复字符 思考：如果模式串的字符两两不相等呢？可以方便快速的编写线性时间的代码 更弱一些的条件：如果模式串的首字符和其他字符不相等呢？10月算法在线班48/挖掘字符串比较的机制10月算法在线班49/分析后的结论 对于模式串的位置j，考察Patternj-1=p0p1.pj-2pj-1，查找字符串Patternj-1的最大相等k前缀和k后缀。注：计算nextj时，考察的字符串是模式串的前j-1个字符，与patternj无关。即：查找满足条件的最大的k，使得 p0p1.pk-2pk-1=pj-kpj-k+1.pj-

21、2pj-110月算法在线班50/求模式串的next21021100-1nextabacbaaba模式串 如：j=5时，考察字符串“abaab”的最大相等k前缀和k后缀10月算法在线班51/next的递推关系 对于模式串的位置j，有nextj=k，即：p0p1.pk-2pk-1=pj-kpj-k+1.pj-2pj-1 则，对于模式串的位置j+1，考察pj：若pk=pj nextj+1=nextj+1 若pkpj 记h=nextk；如果ph=pj,则nextj+1=h+1，否则重复此过程。10月算法在线班52/考察不相等时，为何可以递归下去 若pkpj 记h=nextk；如果ph=pj,则next

22、j+1=h+1，否则重复此过程10月算法在线班53/计算Next数组10月算法在线班54/KMP Code10月算法在线班55/进一步分析next 文本串匹配到i，模式串匹配到j，此刻，若textipatternj，即失配的情况：若nextj=k，说明模式串应该从j滑动到k位置；若此时满足patternj=patternk，因为texti patternj，所以，texti patternk即i和k没有匹配，应该继续滑动到nextk。换句话说：在原始的next数组中，若nextj=k并且patternj=patternk，nextj可以直接等于nextk。10月算法在线班56/Code210月

23、算法在线班57/求模式串的next变种-10-1201-10-1新next21021100-1原始nextabacbaaba模式串10月算法在线班58/理解KMP的时间复杂度 我们考察模式串的“串头”和主串的对应位置(也就是暴力算法中的i)。不匹配：串头后移，保证尽快结束算法；匹配：串头保持不动(仅仅是i+、j+，但串头和主串的对应位置没变)，但一旦发现不匹配，会跳过匹配过的字符(nextj)。最坏的情况，当串头位于N-M的位置，算法结束 因此，匹配的时间复杂度为O(N)，算上计算next的O(M)时间，整体时间复杂度为O(M+N)。10月算法在线班59/考察KMP的时间复杂度 最好情况：当模

24、式串的首字符和其他字符都不相等时，模式串不存在相等的k前缀和k后缀，next数组全为-1 一旦匹配失效，模式串直接跳过已经比较的字符。比较次数为N 最差情况：当模式串的首字符和其他字符全都相等时，模式串存在最长的k前缀和k后缀，next数组呈现递增样式：-1,0,1,2 举例说明10月算法在线班60/KMP最差情况 next:-1 0 1 2 3 比较次数：5 1 1 1 1 周期：n/5 总次数：1.8n 每个周期中:m 1 1 1 周期：n/m 总次数：NNM212 10月算法在线班61/最差情况下，变种KMP的运行情况 next:-1-1-1-1-1 比较次数：5 周期：n/5 总次数：

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

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

27、xt算法，非变种KMP的next算法；要“多”计算到len，即nextlen。思考：如何证明？考察字符串S的k前缀first和k后缀tail：1、first和tail的前p个字符2、first和tail的前2*p个字符3、first和tail的前3*p个字符10月算法在线班66/求字符串周期next字符串序号0cbacbacbacba987654321000-1121110987654321010月算法在线班67/Code10月算法在线班68/思考题：字符串的最长回文子串 回文子串的定义：给定字符串str，若s同时满足以下条件：s是str的子串 s是回文串 则，s是str的回文子串。该算法的要

28、求，是求str中最长的那个回文子串。Manacher算法10月算法在线班69/重建Manacher我们的任务：假定已经得到了前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,

29、Pid,mx)，这个三元组的含义非常明显：所有i个三元组中，向右到达最远的位置，就是mx；3、在计算Pi的时候，考察i是否落在了区间0,mx)中；若i在mx的右侧，说明0,mx)没有能够控制住i，P0.i-1的已知，无法给Pi的计算带来有价值信息；若i在mx的左侧，说明0,mx)控制(也有可能部分控制)了i，现在以图示来详细考察这种情况。10月算法在线班70/思考：BM算法 Boyer-Moore算法是1977年，德克萨斯大学的Robert S.Boyer教授和J Strother Moore教授发明的字符串匹配算法，拥有在最坏情况下O(N)的时间复杂度，并且，在实践中，比KMP算法的实际效能

30、高。BM算法不仅效率高，而且构思巧妙，容易理解。坏字符-好后缀10月算法在线班71/附：坏字符引起的模式滑动 依然从尾部开始比较，发现P与E不匹配，所以P是坏字符。但是，P包含在搜索词EXAMPLE之中。所以，将搜索词后移两位，两个P对齐。10月算法在线班72/附：考虑好后缀10月算法在线班73/面试题 用二进制来编码字符串“uarejulyapp”，需要能够根据编码，解码回原来的字符串，最少需要_位的二进制字符串？仅修改了字符串本身。10月算法在线班74/二叉树的结点 令有2个孩子、1个孩子和0个孩子的结点个数分别为n2、n1、n0 所有结点的出度为2*n2+1*n1+0*n0 除了根结点，

31、其他所有结点的入度都是1，从而所有结点的入度为(n2+n1+n0)-1；总入度等于总出度，2*n2+1*n1+0*n0=n2+n1+n0-1 化简得n0-n2=1 二叉树叶子节点数目比两个孩子的结点数目多1。10月算法在线班75/Huffman编码 Huffman编码是一种无损压缩编码方案。思想：根据源字符出现的(估算)概率对字符编码，概率高的字符使用较短的编码，概率低的使用较长的编码，从而使得编码后的字符串长度期望最小。Huffman编码是一种贪心算法：每次总选择两个最小概率的字符结点合并。称字符出现的次数为频数，则概率约等于频数除以字符总长；因此，概率可以用频数代替。10月算法在线班76/

32、算法演示10月算法在线班77/Code10月算法在线班78/Code10月算法在线班79/Main Code10月算法在线班80/Aux Code10月算法在线班81/Aux Code10月算法在线班82/实验结果10月算法在线班83/Huffman编码总结：前缀编码 Huffman编码是不等长编码字符的编码长度不完全相同。不等长编码如果需要译码，必须满足“前缀编码”的条件：任何一个字符的编码都不是另外一个字符编码的前缀。字符串：ABBC 使用编码方案：A:0B:1C:00 则，ABBC的 编码为：01100 01100的译码可以是ABBC，也可以是ABBAA。10月算法在线班84/Huffm

33、an实现带来的思考 Huffman编码是如何解决前缀编码问题的？实际算法往往是由多个“小算法”堆砌而成的。空格压缩问题取数组最大/小的两个数 代码实现中并非直接使用指针形成的二叉树结点。而是事先开辟足够大的缓冲空间(2n+1)，每次从缓冲区获取一个结点，使用数组代替二叉树。在堆排序、双数组Trie树结构等问题中会再次遇到。最后，由于Huffman树的结点权值(频数)可能相等，因此，对某些文本，Huffman编码不唯一。“左赋1，右赋0”或者“左赋0，右赋1”都可以。10月算法在线班85/字符串查找的思考 字符串和树相结合，往往会产生查找思路上的变革，如Trie树、后缀树(后缀数组)；一个文本文件，大约有一百万行，每行一个词，要求统计出其中最频繁出现的前10个词 将在树、海量数据搜索等章节详细论述。海量数据的字符串查找，往往需要Hash表。在10亿个URL中，查找某URL的出现位置 千万别回答：计算待查找字符串的next数组，用KMP算法。10月算法在线班86/字符串总结 字符串查找：增删改查 KMP/BM map/set：R-BTree Hash Trie树 对字符串本身的操作 全排列 Manacher 回文划分10月算法在线班87/我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班88/感谢大家恳请大家批评指正！