北京7月暑假班第2次课：回文子串KMP等若干问题的讨论邹博.ppt

回文子串-KMP等若干问题的讨论,邹博 2014年7月19日,2/40,字符串循环左移,给定一个字符串S0N-1，要求把S的前k个字符移动到S的尾部，如把字符串“abcdef”前面的2个字符a、b移动到字符串的尾部，得到新字符串“cdefab”：即字符串循环左移k。算法要求：时间复杂度为 O(n)，空间复杂度为 O(1)。,3/40,问题分析,暴力移位法每次循环左移1位，调用k次即可时间复杂度O(kN)，空间复杂度O(1)三次拷贝S0k T0kSk+1N-1 S0N-k-1T0k SN-kN-1时间复杂度O(N)，空间复杂度O(k),4/40,优雅一点的算法,(XY)=YX如：abcdefX=ab X=baY=cdef Y=fedc(XY)=(bafedc)=cdefab时间复杂度O(N)，空间复杂度O(1),5/40,Code,6/40,字符串的全排列,给定字符串S0N-1，设计算法，枚举A的全排列。,7/40,递归算法,以字符串1234为例：1 2342 1343 2144 231,8/40,递归Code,9/40,如果字符有重复,去除重复字符的递归算法以字符1223为例：1 2232 1233 221带重复字符的全排列就是从第一个字符起每个数分别与它后面非重复出现的数字交换。即：第i个数与第j个数交换时，要求i,j)中没有与第j个数相等的数。,10/40,有重复字符的递归,11/40,用空间换时间,如果是单字符，可以使用mark256如果是整数，可以遍历整数得到最大值max和最小值min，使用markmax-min+1如果是浮点数或者其他结构数据，用Hash（事实上，如果发现整数间变化太大，也应该考虑使用Hash；并且，可以认为整数情况是最朴素的Hash）,12/40,全排列的非递归算法,起点：字典序最小的排列，例如12345终点：字典序最大的排列，例如54321过程：从当前排列生成字典序刚好比它大的下一个排列如：21543的下一个排列是23145如何计算？,13/40,21543的下一个排列的思考过程,逐位考察哪个能增大一个数右面有比它大的数存在，它就能增大那么最后一个能增大的数是x=11应该增大到多少？增大到它右面比它大的最小的数y=3应该变为23xxx显然，xxx应由小到大排：145得到23145,14/40,整理成算法语言,步骤：后找、小大、交换、翻转查找字符串中最后一个升序的位置i，即：SkSk+1(ki)，SiSi+1；查找Si+1N-1中比Ai大的最小值Sj；交换Si，Sj；翻转Si+1N-1交换操作后，Si+1N-1一定是降序排列的以926520为例，考察该算法的正确性。,15/40,非递归算法Code,16/40,几点说明,下一个排列算法能够天然的去除重复字符的问题C+STL已经在Algorithm中集成了next_permutation可以将给定在字符串A0N-1首先升序排序，然后依次调用next_permutation直到返回false，即完成了非递归的全排列算法。,17/40,求字符串的最长回文子串,回文子串的定义：给定字符串str，若s同时满足以下条件：s是str的子串s是回文串则，s是str的回文子串。该算法的要求，是求str中最长的那个回文子串。,18/40,解法1 枚举中心位置,int LongestPalindrome(const char*s,int n)int i,j,max;if(s=0|n=0),19/40,算法解析 step1预处理,因为回文串有奇数和偶数的不同。判断一个串是否是回文串，往往要分开编写，造成代码的拖沓。一个简单的事实：长度为n的字符串，共有n-1个“邻接”，加上首字符的前面，和末字符的后面，更n+1的“空”(gap)。因此，字符串本身和gap一起，共有2n+1个，必定是奇数；abbc#a#b#b#c#aba#a#b#a#因此，将待计算母串扩展成gap串，计算回文子串的过程中，只考虑奇数匹配即可。,20/40,数组int Psize,字符串12212321 S=$#1#2#2#1#2#3#2#1#;用一个数组 Pi 来记录以字符Si为中心的最长回文子串向左/右扩张的长度（包括Si），比如S和P的对应关系：S#1#2#2#1#2#3#2#1#P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1Pi-1正好是原字符串中回文串的总长度,21/40,分析算法核心,我们的任务：假定已经得到了前i个值，考察i+1如何计算即：在P0.i-1已知的前提下，计算Pi的值。换句话说，算法的核心，是在P0.i-1已知的前提下，能否给Pi的计算提供一点有用的信息呢？1、通过简单的遍历，得到i个三元组k,Pk,k+Pk，0ki-12、可以挑选出这i个三元组中，k+Pk最大的那个三元组，不妨记做(id,Pid，Pid+id)。进一步，为了简化，记mx=Pid+id，因此，得到三元组为(id,Pid,mx)，这个三元组的含义非常明显：所有i个三元组中，向右到达最远的位置，就是mx；3、在计算Pi的时候，考察i是否落在了区间0,mx)中；4、若i在mx的右侧，说明0,mx)没有能够控制住i，P0.i-1的已知，无法给Pi的计算带来有价值信息；5、若i在mx的左侧，说明0,mx)控制（也有可能部分控制）了i，现在以图示来详细考察这种情况。,22/40,Manacher递推关系,记i关于id的对称点为j(=2*id-i)，若此时满足条件mx-iPj：记my为mx关于id的对称点(my=2*id-mx)；由于以Sid为中心的最大回文子串为Smy+1idmx-1，即：Smy+1,id与Sid,mx-1对称，而i和j关于id对称，Pj已知，因此Pi=Pj。,23/40,Manacher递推关系,记i关于id的对称点为j(=2*id-i)，若此时满足条件mx-iPj：记my为mx关于id的对称点(my=2*id-mx)；由于以Sid为中心的最大回文子串为Smy+1idmx-1，即：Smy+1,id与Sid,mx-1对称，而i和j关于id对称，Pj已知，因此Pi至少等于mx-i（图中绿色框部分）。,24/40,Manacher Code,25/40,关于原始算法重要改进,Pj mx i：Pi=mx iPj mx i：Pi=PjPj=mx i：Pi Pj,26/40,Manacher改进版,27/40,KMP算法,串查找问题：给定原始串S和模式串P，查找从字符串S中第一次出现P的位置。最基本的字符串匹配算法暴力求解(Brute-Force)：O(m*n)；KMP算法是一种线性时间复杂的字符串匹配算法，它是对BF算法改进。BF算法的时间复杂度O(strlen(S)*strlen(T)，空间复杂度O(1)。KMP算法的时间复杂度O(strlen(S)+strlen(T)，空间复杂度O(strlen(T)。,28/40,暴力求解,29/40,分析BF与KMP的区别,假设现在S串匹配到i位置，T串匹配到j位置。BF算法中，如果当前字符匹配成功，即si+j=Tj，令i+，j+，继续匹配下一个字符；如果失配，即Si+j!=Tj，令i+，j=0，即每次匹配失败的情况下，模式串T相对于原始串S向右移动了一位。KMP算法中，如果当前字符匹配成功，即Si+j=Tj，令i+，j+，继续匹配下一个字符；如果失配，即Si+j!=Tj，令i不变，j=nextj，(nextj=1),30/40,描述性说法,在暴力求解中，为什么模式串的索引会回溯？因为模式串存在重复字符如果模式串的字符两两不相等呢？更弱一些的条件：如果模式串的首字符和其他字符不相等呢？对于Pj=p0 p1.pj-1 pj，查找字符串Pj的最大相等k前缀和k后缀。即：查找满足条件的最大的k，使得p0 p1.pk-1 pk=pj-k pj-k+1.pj-1 pj,31/40,求模式串的next,32/40,next的递推关系,计算next函数的方法可以采用递推，如果对于值ka0 a1.ak-1 ak=aj-k aj-k+1.aj-1 aj则对于pattern的前j+1序列字符，则若patternk+1=patternj+1nextj+1=next(j)+1若patternk+1patternj+1记h=nextk；如果此时patternh+1=patternj+1,则nextj+1=h+1否则重复此过程。,33/40,KMP,34/40,KMP Code,35/40,考察KMP的时间复杂度,我们考察模式串的“串头”和主串的对应位置（也就是暴力算法中的i）。不匹配：串头后移，保证尽快结束算法；匹配：串头保持不动（仅仅是i+、j+，但串头和主串的对应位置没变），但这个没有关系。一旦发现不匹配了地方，会跳过匹配过的字符(nextj)。最坏的情况，当串头位于N-M的位置，算法结束因此，匹配的时间复杂度为O(N)，算上计算next的O(M)时间，整体时间复杂度为O(M+N)。,36/40,KMP的几点说明,网络上有大量介绍KMP的文章，在提供光辉思想的同时，常常有些不太准确的表述。需要自我辨别。如：我们可以预见KMP算法的均摊复杂度是O(n+m)，为什么呢？因为你的s串是不会回退的，因此最多访问了n次，而模式串pattern在每一次匹配中的走动均摊下来近似为O(m)的，因此总的复杂度为O(n+m)。这种解释是不正确的。该算法最经济实惠的理解方法是编程实践；经典KMP有改进算法，计算得到的next数组能够更小，使得模式串更快的向后匹配；BM算法等其他字符串快速匹配算法。,37/40,PowerString问题,给定一个长度为n的字符串S，如果存在一个字符串T，重复若干次T，能够得到S，那么，S叫做周期串，T叫做S的一个周期。如：字符串abababab是周期串，abab、ab都是它的周期，其中，ab是它的最小周期。设计一个算法，计算S的最小周期。如果S不存在周期，返回空串。,38/40,使用next，线性时间解决问题,计算S的next函数；记k=nextlen-1，p=len-k；若len能够整除p，则p就是最小周期长度，前p个字符就是最小周期。如何证明？,39/40,BM算法,Boyer-Moore算法是1977年，德克萨斯大学的Robert S.Boyer教授和J Strother Moore教授发明的字符串匹配算法，拥有在最坏情况下O(N)的时间复杂度，并且，在实践中，比KMP算法的实际效能高。BM算法不仅效率高，而且构思巧妙，容易理解。,40/40,举例说明BM算法的运行过程,41/40,坏字符,首先，字符串与搜索词头部对齐，从尾部开始比较。这是一个很聪明的想法，因为如果尾部字符不匹配，那么只要一次比较，就可以知道前7个字符肯定不是要找的结果。我们看到，S与E不匹配。这时，S就被称为坏字符（bad character），即不匹配的字符。我们还发现，S不包含在搜索词EXAMPLE之中，这意味着可以把搜索词直接移到S的后一位。,42/40,坏字符引起的模式滑动,依然从尾部开始比较，发现P与E不匹配，所以P是坏字符。但是，P包含在搜索词EXAMPLE之中。所以，将搜索词后移两位，两个P对齐。,43/40,坏字符规则,后移位数=坏字符位置-坏字符在搜索词中的最右出现的位置如果坏字符不包含在搜索词之中，则最右出现位置为-1以“P”为例，它作为“坏字符”，出现在搜索词的第6位（从0开始编号），在搜索词中的最右出现位置为4，所以后移6-4=2位。再以前面的S为例，它出现在第6位，最右出现位置是-1（即未出现），则整个搜索词后移6-(-1)=7位。,44/40,好后缀,依次比较，得到“MPLE”匹配，称为好后缀（good suffix），即所有尾部匹配的字符串。注意，MPLE、PLE、LE、E都是好后缀。,45/40,遇到坏字符,发现“I”与“A”不匹配：“I”是坏字符。根据坏字符规则，此时搜索词应该后移2-(-1)=3位。问题是，有没有更优的移法？,46/40,考虑好后缀,47/40,好后缀规则,后移位数=好后缀的位置-好后缀在搜索词其余部分中最右出现位置如果好后缀在搜索词中没有再次出现，则为-1。所有的“好后缀”（MPLE、PLE、LE、E）之中，只有“E”在“EXAMPL”之中出现，所以后移6-0=6位。“坏字符规则”只能移3位，“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数，只与搜索词有关，与原字符串无关。,48/40,坏字符,继续从尾部开始比较，“P”与“E”不匹配，因此“P”是“坏字符”。根据“坏字符规则”，后移 6-4=2位。因为是最后一位就失配，尚未获得好后缀。,49/40,参考文献,余祥宣等，计算机算法基础M，华中科技大学出版社，2001https:/(最长回文子串)http:/(最长回文子串)http:/（KMP）http:/（KMP）http:/,50/40,感谢大家！欢迎大家提出宝贵的意见！,