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

回文子串-KMP等若干问题的讨论 邹博 2014年7月19日 字符串循环左移 给定一个字符串S[0…N-1]，要求把S的前k个字符移动到S的尾部，如把字符串“abcdef”前面的2个字符‘a’、‘b’移动到字符串的尾部，得到新字符串“cdefab”：即字符串循环左移k。 算法要求： 时间复杂度为 O(n)，空间复杂度为 O(1)。 问题分析 暴力移位法 每次循环左移1位，调用k次即可 时间复杂度O(kN)，空间复杂度O(1) 三次拷贝 S[0…k] → T[0…k] S[k+1…N-1] → S[0…N-k-1] T[0…k] →S[N-k…N-1] 时间复杂度O(N)，空间复杂度O(k) 优雅一点的算法 (X’Y’)’=YX 如：abcdef X=ab X’=ba Y=cdef Y’=fedc (X’Y’)’=(bafedc)’=cdefab 时间复杂度O(N)，空间复杂度O(1) Code 字符串的全排列 给定字符串S[0…N-1]，设计算法，枚举A的全排列。 递归算法 以字符串1234为例： 1 – 234 2 – 134 3 – 214 4 – 231 递归Code 如果字符有重复 去除重复字符的递归算法 以字符1223为例： 1 – 223 2 – 123 3 – 221 带重复字符的全排列就是从第一个字符起每个数分别与它后面非重复出现的数字交换。 即：第i个数与第j个数交换时，要求[i,j)中没有与第j个数相等的数。 有重复字符的递归 用空间换时间 如果是单字符，可以使用mark[256] 如果是整数，可以遍历整数得到最大值max和最小值min，使用mark[max-min+1] 如果是浮点数或者其他结构数据，用Hash（事实上，如果发现整数间变化太大，也应该考虑使用Hash；并且，可以认为整数情况是最朴素的Hash） 全排列的非递归算法 起点：字典序最小的排列，例如12345 终点：字典序最大的排列，例如54321 过程：从当前排列生成字典序刚好比它大的下一个排列 如：21543的下一个排列是23145 如何计算？ 21543的下一个排列的思考过程 逐位考察哪个能增大 一个数右面有比它大的数存在，它就能增大 那么最后一个能增大的数是——x = 1 1应该增大到多少？ 增大到它右面比它大的最小的数——y = 3 应该变为23xxx 显然，xxx应由小到大排：145 得到23145 整理成算法语言 步骤：后找、小大、交换、翻转—— 查找字符串中最后一个升序的位置i，即：S[k]S[k+1](ki)，S[i]S[i+1]； 查找S[i+1…N-1]中比Ai大的最小值Sj； 交换Si，Sj； 翻转S[i+1…N-1] 交换操作后，S[i+1…N-1]一定是降序排列的 以926520为例，考察该算法的正确性。 非递归算法Code 几点说明 下一个排列算法能够天然的去除重复字符的问题 C++STL已经在Algorithm中集成了next_permutation 可以将给定在字符串A[0…N-1]首先升序排序，然后依次调用next_permutation直到返回false，即完成了非递归的全排列算法。 求字符串的最长回文子串 回文子串的定义： 给定字符串str，若s同时满足以下条件： s是str的子串 s是回文串 则，s是str的回文子串。 该算法的要求，是求str中最长的那个回文子串。 解法1 – 枚举中心位置 int LongestPalindrome(const char *s, int n) { int i, j, max; if (s == 0 || n 1) return 0; max = 0; for (i = 0; i n; ++i) { // i is the middle point of the palindrome for (j = 0; (i - j = 0) (i + j n); ++j) // if the length of the palindrome is odd if (s[i - j] != s[i + j]) break; if (j * 2 + 1 max) max = j * 2 + 1; for (j = 0; (i - j = 0) (i + j + 1 n); ++j) // for the even case if (s[i - j] != s[i + j + 1]) break;