【学习笔记】最小表示法

用途

给定一个长度为n，可旋转的字符串环，求从哪个位置断开的长度为n的字符串字典序最小/大(以最小为例，最大同理)

算法描述
- 令i=0,j=1表示最小的字符串可能的位置；
- 找到一个k使得s[i+1]==s[j+1],s[i+2]==s[j+2] ,..., s[i+k-1]==s[j+k-1] ;
- 但是s[i+k]!=s[j+k];
- 如果此时s[i+k]<s[j+k]，对于j' = j + 1 到 j + k 的位置一定不是最优解，因为i+j'-j位置的串一定比j'位置的更优；且如果i+j'-j位置的串更优一定会被i选到。那么我们就可以 j=j+k+1
- s[i+k]>s[j+k]就i=i+k+1,注意i==j时要再向后移动一位
- 事实上你可以理解成i和j是互相独立的只是其中的某一个为最小的串的待定值，另一个为用来比较的串；
复杂度
- 每多匹配一位k，i或j一次跳跃的次数就会相应多一位，最多跳2*k，所以复杂度O(n)；
bzoj1398 Vijos1382寻找主人 Necklace

　　　　当求出最小表示法之后，扫一遍即可比较两个不可翻转的环是否本质相同，比较本质应该是其常见用途吧；

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #include<cmath>
 7 #include<vector>
 8 #include<stack>
 9 #include<map>
10 #include<set>
11 #define Run(i,l,r) for(int i=l;i<=r;i++)
12 #define Don(i,l,r) for(int i=l;i>=r;i--)
13 #define ll long long
14 #define ld long double
15 #define inf 0x3f3f3f3f
16 #define mk make_pair
17 #define fir first
18 #define sec second
19 #define il inline
20 #define rg register
21 #define pb push_back
22 using namespace std;
23 const int N=2000010;
24 int n;
25 char s[N],t[N];
26 int cal(char *S){
27     int i= 0, j = 1 ,k;
28     while(i<n&&j<n){
29         for(k=0;S[i+k]==S[j+k];k++);
30         if(S[i+k]<S[j+k]){j+=k+1;if(i==j)j++;}
31         else {i+=k+1;if(i==j)i++;}
32     }
33     return min(i,j);
34 }
35 int main(){
36     freopen("bzoj1398.in","r",stdin);
37     freopen("bzoj1398.out","w",stdout);
38     scanf("%s%s",s,t);
39     n = strlen(s);
40     for(rg int i=0;i<n;i++)s[i+n] = s[i] , t[i+n] = t[i];
41     int pos1 = cal(s);
42     int pos2 = cal(t);
43     int fg=1;
44     for(rg int i=0;i<n;i++){
45         if(s[pos1+i]!=t[pos2+i]){fg=0;break;}
46     }
47     if(!fg){puts("No");}
48     else {
49         puts("Yes");
50         for(rg int i=0;i<n;i++){
51             putchar(s[pos1+i]);
52         }
53     }
54     return 0;
55 }//by tkys_Austin;

bzoj1398

【学习笔记】最小表示法

用途

算法描述

复杂度