最小表示法及其证明

问题

对于一个字符串S,求S的循环的同构字符串S’中字典序最小的一个。

我们举例说明,字符串"abcd"的循环同构字符串有:["abcd", "bcda", "cdab", "dabc"]

题目的目标是求这些字符串中字典序最小的那个。

暴力解法

暴力解法非常直观,直接枚举字符串的起点,然后找到构成最小字符串的那一个。

代码就不在这里写了。

最小表示法

最小表示法是解决同构字符串最小表示的巧妙算法。

其算法描述如下:

令i=0,j=1
如果S[i] > S[j] i=j, j=i+1
如果S[i] < S[j] j++
如果S[i] == S[j] 设指针k,分别从i和j位置向下比较,直到S[i] != S[j]
         如果S …
more ...