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

1、回文子串-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 T0k Sk+1N-1 S0N-k-1 T0k SN-kN-1 时间复杂度O(N)，空间复杂度O(k),4/40,优雅一点的算法,(XY)=YX 如：abcdef X=ab X=ba Y=cdef Y=fedc (XY)=(bafedc)=cdefab 时间复杂度O(N)，空间复杂度O(1),5/40,Code,6/40,字符串的全排列,给定字符串S0N-1，设计算法，枚举A的全排列。,7/40,递归算法,以字符串1234为例： 1 234 2 134 3 214 4 231,8/40,递归Code,9/40,如果字符有重复,去除重复字符的

2、递归算法 以字符1223为例： 1 223 2 123 3 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 = 1 1应该增大到多少？ 增大到它右面比它大的最小的数y = 3 应该变为23xxx 显然，xxx应由小到大排

3、：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 (

4、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 1 Pi-1正好是原字符串中回文串的总长度,21/40,分析算法核心,我们的任务：假定已经得到了前i个值，考察i+1如何计算 即：在P0.i-1已知的前提下，计算Pi的

5、值。换句话说，算法的核心，是在P0.i-1已知的前提下，能否给Pi的计算提供一点有用的信息呢？ 1、通过简单的遍历，得到i个三元组k,Pk,k+Pk，0ki-1 2、可以挑选出这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，P0i-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。

6、,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 i Pj mx i：Pi = Pj Pj = 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

7、,暴力求解,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函数的方法可以采用递推，如果对于值k a0 a1 .ak-1 ak = aj-k aj-k+1.

8、aj-1 aj 则对于pattern的前j+1序列字符，则 若patternk+1=patternj+1 nextj+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串是不会回退的，因此最多访问

9、了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“不包含

《北京7月暑假班第2次课：回文子串-kmp等若干问题的讨论邹博》由会员san****019分享，可在线阅读，更多相关《北京7月暑假班第2次课：回文子串-kmp等若干问题的讨论邹博》请在金锄头文库上搜索。