字符串最小表示算法

Veröffentlicht am   |  

同构字符串

首先来看下什么是同构字符串。考虑字符串“abc”，将它循环移位，可以得到“bca”,“cab”。这些通过对原字符串进行循环移位得到的字符串以及它自身，成为原字符串的同构字符串。

而字符串的最小表示法就是指它的所有同构字符串中按字典序排列排在最小位置的那个。比如“abc”的最小表示就是它本身（类似可以定义最大表示法）。

Naive Algorithm

要求某个字符串的最小表示，最容易想到的就是对它的所有同构字符串进行穷举。为了说明方便，先规定以下符号：

用一个大写字母，比如S代表一个字符串
S[i] 代表S的第i个字符，并且第一个字符为S[0]。
S[i,j]表示S的一个从i开始到j结束的子串（包含i,j)。
S+T代表将S和T连接并且S在前组成新字符串。
|S|表示S的长度

穷举S所有的同构串有一个技巧。观察S+S,我们会发现其中出现了S的所有的同构串，所以可以对S+S进行穷举可以避免求模运算。

1
2
3
4
5
6
7
8
9
10
11
12
len = |S|
S = S + S
i = 0
for j = 0 to len-1:
    for k = 0 to len:
        if S[i+k] > S[j+k]
            i = j
            k = 0
            break
        else
            k = 0
            break

易得，以上算法的对S+S进行穷举，最坏情况下时间复杂度为$O(n^2)$。

A better approach

上面的暴力算法在小数据情况下已经足够用，但是遇到更大的数据（比如百万级）， 平方级别算法显然是不适用的。

周源利用了字符串之间的信息，提出了一种$O(n)$的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    int minimumExpression(string s) {
            s = s + s;
            int len = s.size(), i = 0, j = 1, k = 0;
            while(i + k < len && j + k < len) {
                    if(s[i+k] == s[j+k]) k++;
                    else if(s[i+k] > s[j+k])
                    { 
                        i = i+k+1; 
                        k = 0; 
                    }
                    else if(s[i+k] < s[j+k]) 
                    { 
                        j = j+k+1; 
                        k = 0; 
                    }
                    if (i == j)
                        j++;
   }
   return i < j ? i : j;
}

为了理解这个算法，举个例子。

当比较从i和j开始的子串的大小时，从i开始的子串比从j开始的小，也就意味着对于$ 0\le p \lt k$,$S[i+p]=S[j+p]$并且$S[i+k] < S[j+k]$。那么我们可以得出这么个结论：从j+p开始的子串（$ 0\le p \le k$)不可能是最小表示。因为对于任何从j+p开始的子串，从i+p开始的子串总是比它小 ，因此我们可以跳过这一段，直接从j+k+1开始匹配。
算法的复杂度很好证明，因为每一轮比较都比较k次，并且指针向前移动k个位置，所以时间复杂度是$O(n)$。

算法正确性证明

引理1：设i < j， 所有以i到j之间开头的同构字符串不比以i开头的大。
证明：（一旦$i \gt j$,由于具有对称性，将i和j调换，不影响证明）
以i和j之间的字符个数表示相应的状态，比如考虑初始状态，i = 0,j = 1,k = 0，这时处于状态0。开始有三种情况：

1、$S[i] = S[j]$，k = k + 1，此时i和j之间没有字符，没有离开初始状态。
2、$S[i] < S[j] = S[i+1]$, j = j + 1, 之间的字符为S[i+1],显然成立。
3、$S[i] > S[j] , i = 1,j =2,回到初始状态。

那么接下来有两种情况，
1、 处于状态0。这种情况不需要证明。
2、 离开状态0，到达状态k。

现在考虑第二种情况。假如从0到达k状态，由于之前一直处于状态0，意味着S[i+p] = Si。现在到达了状态1，说明S[i+k] < S[i]（如果S[i+k] > S[i],则将i和j调换）。不变式成立。

那么接下来以状态k为初始状态进行证明。
这时有三种情况：
1、停留在k状态
2、到达t < k状态
3、 到达t > k状态
这三种情况分别对应S[i+k-t]等于，大于，小于S[j+k-t]的情况。
//TODO