本文共 944 字，大约阅读时间需要 3 分钟。
问题A：
字符串正则匹配：见：
问题B：
旋转字符串判断：将字符串前面任意部分挪到后面形成新字符串，则新旧字符串互为旋转字符串。
思维+KMP，时间O(N)
将某一字符串变为2倍长，首尾拼接，则旋转字符串一定在其之间。问题C：
AC自动机。见：
问题D：
字符串旋转，要求空间复杂度为O(1)思维，时间O(N)
例如：ABCDE -> DEABC步骤如下：ABCDE -> CBADE -> CBAED -> DEABC
或者，二分思想：
例如：1234567ABCD -> ABCD1234567每次选取较短部分进行交换。
步骤如下：1234567ABCD -> ABCD5671234 -> ABCD2341567 -> ABCD1342567 -> ABCD1243567 -> ABCD1234567问题E：
完美洗牌问题，空间要求O(1)将 {L1,L2,L3,R1,R2,R3} -> {R1,L1,R2,L2,R3,L3}
思维，下标连续推，时间O(N)
长度2*N的数组，可以由数个(3^ka-1), (3 ^kb -1)…长度的子数组组成。
长度为3^k -1 的数组有规律，通过下标连续推可以形成数个环，每个环的起始位置为1，3，9，…，3 ^(k-1)。
问题F：
将一个数组调整成{a,b,c,d,e} 使之满足 a<=b>=c<=d>=e，要求空间O(1)思维，时间O(N*logN)
先将数组排序，然后构造{L1,R1,L2,R2…}即可。
注，完美洗牌问题只能构造{R1,L1,R2…}，所以使用完美洗牌后，再将相邻两个交换，例如L1和R1。问题G:
旋变字符串：
每个字符都作为叶结构可以构成一棵树，拥有公共父节点都串可以左右交换，称为旋变字符串，判断两个串是否互为旋变字符串。dp，时间O(NNN*N)
dp[i][j][k] 代表strA[i…i+k] 和 strB[j…j+k] 是否为旋变串。 dp[0][0][N]即为所求答案。dp填一个四棱锥，高为K，长宽各为i和j
每个点依赖平行于i面和j面的斜线。故而，四重循环最外层从下向上，内两层铺i*j的面，最内层枚举k。
问题H：
最大回文子串的Manacher算法，见转载地址：http://lbwji.baihongyu.com/