首页 > 代码库 > 最小表示法(模板)

最小表示法(模板)

最小表示法就是对于一个循环字符串,其字典序最小的状态;

显然任意一个循环串的最小表示法是唯一的,那么可以同过比较两个循环串的最小表示法来判断它们是否相同;

 

对于朴素算法:

初始化:i = 0, j = 1, k = 0;

若 s[i] < s[j],j++;

若 s[i] > s[j],i = j, j++;

若 s[i] == s[j],则 k++,直至 s[i + k] != s[j + k]

  对于 s[i + k] < s[j + k],j++;

  否则 i = j, j++;

返回 min(i, j);

 

时间复杂度 O(n^2),其中 n 为字符串 s 的长度;

 

代码:

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

 

优化:

 s[i + k] != s[j + k]时:

对于 s[i + k] > s[j + k], 可直接令 i += k + 1;

关于其正确性证明:

i += k + 1 可行,只需证明 1) 以 i ~ i + k 中字符为头首字符的串不可能字典序最小;

证明 1) ,只需证明 2) 对于以 i ~ i + k 开头,以 i + k 结尾的后缀,一定存在等长的子串字典序比其小;

证明 2): 任取 i <= i‘ <= i + k,构造子串 s[i‘, i + k],len = i  + k - i‘ + 1;取与其等长子串 s[j + k - len + 1 , j + k];

显然有:s[i‘, i + k - 1] = s[j + k - len + 1, j + k - 1] && s[i + k] > s[j + k],所以 s[i‘, i + k] > s[j + k - len + 1, j + k];

所以结论 2) 得证,即结论 1) 得证;

 

对于 s[i + k] < s[j + k],可令 j += k + 1 ;

其正确性证明与上面类似:

j += j + 1 可行,只需证明 1) 以 j ~ j + k 中字符为头首字符的串不可能字典序最小;

证明 1) ,只需证明 2) 对于以 j ~ j + k 开头,以 j + k 结尾的后缀,一定存在等长的子串字典序比其小;

证明 2): 任取 j <= j‘ <= j + k,构造子串 s[j‘, j + k],len = j  + k - j‘ + 1;取与其等长子串 s[i + k - len + 1 , i + k];

显然有:s[j‘, j + k - 1] = s[i + k - len + 1, i + k - 1] && s[j + k] > s[i + k],所以 s[j‘, j + k] > s[i + k - len + 1, i + k];

所以结论 2) 得证,即结论 1) 得证;

 

注意:若出现 i == j 的情况,则将 j 往后移一位;

 

时间复杂度 O(n),其中 n 为字符串 s 的长度;

 

代码:

技术分享
 1 void get_min(int n, int m){//最小表示法
 2     int i = 0, j = 1 ,k = 0, t;
 3     while(i < m && j < m && k < m){
 4         t = a[n][(i + k) % m] - a[n][(j + k) % m];
 5         if (!t) k++;
 6         else{
 7             if(t > 0) i += k + 1;
 8             else j += k + 1;
 9             if (i == j) j++;
10             k = 0;
11         }
12     }
13     a[n][m] = i < j ? i : j;
14 }
View Code

 

最小表示法(模板)