循环字符串的最小表示(自学)

循环字符串的最小表示

drizzlecrj整理

循环同构问题：给出两个串：s1 = “babba”和s2 = “bbaba”，其中两者均看成环状的，即首尾是相接的，问：从s1的哪里断开可以得到和s2一样的串或者两者用不会相同？本题就是从s1的第2个字符’a’后面断开，可以得到与s2一样的串。这个问题就是同构问题。下面一步一步分析：

1．朴素算法(O(nm))：即尝试s1的n个断开点，与s2进行比较，如果相同则找到同构位置，否则找不到。该算法仅适用于n, m规模较小情况，对于n, m 都在10000规模的长度，明显速度太慢。

2．转换为模式匹配：对于此类问题，已经有一个很好的转换思路了，即：首先构造新的模型：S=s1+s1为主串，s2为模式串。如果s1和s2是循环同构的，那么s2就一定可以在S中找到匹配。否则找不到匹配则两则不能同构。而在S中寻找s2的匹配是有很多O(N+M)级的算法了，KMP算法就是这样一个优秀的算法，所以本问题转换为模式匹配后应用KMP算法，可以在O(n+m)的时间内获得问题的解。

3．下面再来看看“最小表示法”在此类问题中的应用（算法思路来源于国家队的一位队员--周源），它也可以在O(n+n)时间内求解，更大的优势还有无需KMP算法的Next数组，仅需要两个指针即可。

一．从小问题谈起：

问题：有两列数a1,a2…an和b1,b2…bn ，不记顺序，判断它们是否相同。eg：{an} = {2, 3, 5, 7}；{bn} = {2, 7, 5 3}。一眼可见两者是相同的，但是对于计算机来说，如果采用枚举算法，那么比较次数将是：n*(n-1)*(n-2)….*2*1 = n! 量级。阶乘增长之快，时间上是无法忍受的。抓住问题的本质：如果两列数相同，那么它们排序之后从头到尾肯定一样！则问题在O(nlogn)时间解决。可见这个问题的本质就在于排序（非降序）之后的序列是原序列的“最小表示”，如果两个序列的“最小表示”相同则两者就相同，否则就不相同。

启示：当两个对象有多种形式且需判断它们在某种变换规则下是否相同时，可转换为比较可以通过变换规则得到的所有表示的“最小表示”是否相同。例如本问题是不计顺序的规则，最小表示就是非降序排列后的序列。当然对于其它问题就不能简单的排序了，需要满足“在变换规则下可以达到的表示形式”。

二．最小表示法

1．首先定义一个变换规则f，判断两个事物s和t是否互为f本质相同，方法就是：将s，t转换为规则f下的最小表示形式，再比较是否相同。

2．返回到本节一开始提到的字符串循环同构问题，规则f就是“循环移动”，最直接最简单

的方法就是分别求出s1, s2的最小表示，再比较两者是否相同，但是可以发现这明显也是一个O(n^2)思路。

3．换一种思路，令Min(s)返回值为：从s的第Min(s)个字符引起的s的一个循环表示的最小表示，若有多个值则返回下标最小的一个。例如s = {bbbaab}，那么Min(s) = 3 --下标从0算起。Min(s)的求法在后面部分具体阐述，这个问题仅仅用到这个概念，不必直接求，因为当找到循环同构时实际就是Min(s)。

4．先类似于模式匹配方法将两者加倍：u = s1 + s1，w = s2 + s2，指针i，j分别指向u, w的第一个位置0，i，j指针滑动可以得到两种情况：

(1) 若i，j分别指向Min(s1)和Min(s2)时，一定有u[i…i+|s1|-1] = w[j…j+|s2|+1]也就是立马得到解。

(2) 否则i

因此问题转换为：两个指针分别向后滑动比较，如果比较失败，如何正确的滑动指针使得新指针i, j仍然满足：i=0)，即有u[i+k]≠w[j+k]。仍然分两种情况：

(1) u[i+k] > w[j+k]：令iw[j+k]，因此整个s[x-1]都不是s1的最小表示的前缀，则Min(s1)>i+k，所以i可以滑动到i+k+1仍可保证

(2) 同样的分析，如果u[i+k]

综上，也就是说，两指针向后滑动比较失败以后，指向较大字符的指针向后滑动k+1个位置，直到出现如下情况：

(1) 最后两指针指向的位置，向后面(包括自身起始位置)比较了len个字符都匹配成功时，那两个位置i, j就分别是s1和s2的“最小表示”的位置；

(2) 或者i, j两个指针其中一个移动到>= len的位置，那么表示s1和s2无法循环同构。以实例分析，假设s1=‘babba’，s2=‘bbaba’。那么有

u = ‘b a b b a b a b b a’

w = ‘b b a b a b b a b a’

按照上面分析的方法，i，j指针都指向0，然后滑动，那么在i = 4, j = 2时会出现连续5

个字符相等：u[4→8] = w[2→6]，所以s1和s2是循环同构的，同构位置在s1的i = 4，s2的j = 2处。实际也都是它们最小表示的位置。

至此，循环同构的这个O(n)级的算法介绍完毕，不得不说提出这个算法思想的人属于天才级别的，很类似于KMP的思路，但是却仅适用两个指针实现了O(n)的算法。下面将分别就这个算法，展开两个问题的具体求解。

1．求字符串的循环最小表示：

上面说的两个字符串同构的，并没有直接先求出Min(s)，而是通过指针移动，当某次匹配串长时，那个位置就是Min(s)。而这里的问题就是：不是给定两个串，而是给出一个串，求它的Min(s)，eg：Min(“babba”) = 4。那么由于这里并非要求两个串的同构，而是直接求它的最小表示，由于源串和目标串相同，所以处理起来既容易又需要有一些变化：我们仍然设置两个指针，p1, p2，其中p1指向s[0]，p2指向s[1]，仍然采用上面的滑动方式：

(1) 利用两个指针p1, p2。初始化时p1指向s[0], p2指向s[1]。

(2) k = 0开始，检验s[p1+k] 与 s[p2+k] 对应的字符是否相等，如果相等则k++，一直下去，直到找到第一个不同，(若k试了一个字符串的长度也没找到不同，则那个位置就是最小表示位置，算法终止并返回)。则该过程中，s[p1+k] 与 s[p2+k]的大小关系，有三种情况：

(A). s[p1+k] > s[p2+k]，则p1滑动到p1+k+1处 --- 即s1[p1->p1+k]不会

是该循环字符串的“最小表示”的前缀。

(B). s[p1+k]

(C). s[p1+k] = s[p2+k]，则 k++； if (k == len) 返回结果。

注:这里滑动方式有个小细节，若滑动后p1 == p2，将正在变化的那个指针再+1。直到p1、p2把整个字符串都检验完毕，返回两者中小于 len 的值。

(3) 如果 k == len， 则返回p1与p2中的最小值

如果 p1 >= len 则返回p2

如果 p2 >= len 则返回p1

(4) 进一步的优化，例如：p1要移到p1+k+1时，如果p1+k+1

至此，求一个字符串的循环最小表示在O(n)时间实现，感谢大牛的论文。其中实现时的小细节“如果滑动后p1 == p2，将正在变化的那个指针再+1”，开始没有考虑，害得我想了几个小时都觉得无法进行正确的移动。具体例题有两个：http://acm.zju.edu.cn 的2006和1729题。一个是10000规模一个是100000规模。运行时间前者是0S，后者是0.05S。