数据结构-字符串.pptx

字符串 数据结构-字符串全文共87页，当前为第1页。 字符串 字符串的范畴非常广泛； 难题往往在此节出现； 掌握字符串的法门是 。 字符串问题的晦涩代表：KMP、Manacher 数据结构-字符串全文共87页，当前为第2页。 主要内容 需要掌握的内容 字符串循环左移 LCS最长递增子序列 字符串全排列 递归、非递归 KMP Huffman编码 需要了解的内容 Manacher算法 BM算法 数据结构-字符串全文共87页，当前为第3页。 字符串循环左移 4/88 给定一个字符串S[0…N-1]，要求把S的前k 个字符移动到S的尾部，如把字符串"abcdef" 前面的2个字符'a'、'b'移动到字符串的尾 部，得到新字符串"cdefab"：即字符串循环 左移k。 多说一句：循环左移k位等价于循环右移n-k位。 算法要求： 时间复杂度为 O(n)，空间复杂度为 O(1)。 数据结构-字符串全文共87页，当前为第4页。 问题分析 5/88 暴力移位法 每次循环左移1位，调用k次即可 时间复杂度O(kN)，空间复杂度O(1) 三次拷贝 S[0…k] T[0…k] S[k+1…N-1] S[0…N