最大最小表示法

算法用途：

一个首位相连的字符串，我们要寻找一个位置，以这个位置为起点的新字符串，我们需要使这个字符串字典序最小。

比如abcde，以c为开头的话就是cdeab

字典序：

两个串的字典序大小比较，是从第一个字母往最后一个比较，如果同一个位置字符相同就可以比较下一位，否则两个字符中哪个字符ascall值大的哪个串字典序就大

最小表示法代码：

 1 int getmin()
 2 
 3 {
 4 
 5     int n = strlen(s);
 6 
 7     int i = 0,j = 1,k = 0,t;
 8 
 9     //表示从i开始k长度和从j开始k长度的字符串相同
10 
11     while(i < n && j < n && k < n)
12 
13     {
14 
15         t = s[(i+k)%n] - s[(j+k)%n];
16 
17         //t用来计算相对应位置上那个字典序较大
18 
19         if(!t) k++;//字符相等的情况
20 
21         else
22 
23         {
24 
25             if(t > 0) i += k+1;//i位置大,最大表示法: j += k+1
26 
27             else j += k+1;//j位置大,最大表示法: i += k+1
28 
29             if(i == j) j++;
30 
31             k = 0;
32 
33         }
34 
35     }
36 
37     return i >j ?j :i;
38 
39 }

View Code

最大最小表示法：

 1 int getminmax(int flag,char word[])  //最小最大表示法0、1
 2 
 3 {
 4 
 5     int i=0,j=1,k=0;
 6 
 7     int wlen=strlen(word);
 8 
 9     while(i<wlen&&j<wlen&&k<wlen)
10 
11     {
12 
13         int t=word[(i+k)%wlen]-word[(j+k)%wlen];
14 
15         if(!t) k++;
16 
17         else
18 
19         {
20 
21             if(flag==0)  //求最小字典序 
22 
23             {
24 
25                 if(t>0) i=i+k+1;
26 
27                 else    j=j+k+1;
28 
29             }
30 
31             else  //求最大字典序 
32 
33             {
34 
35                 if(t>0) j=j+k+1;
36 
37                 else    i=i+k+1;
38 
39             }
40 
41             if(i==j)    j++;
42 
43             k=0;
44 
45         }
46 
47     }
48 
49     return i<j?i:j;
50 
51 }//返回的是从0开始的位置

View Code

最小表示法例题：HDU 2609 How many传送门

题意：

给出n个由0/1组成的首尾相连的串，通过循环可以相同的串算一类，求一共有几类串。

题解：

把所有串都用最小表示法找到每一个串的最小字典序，看一样有几个不相同的

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<set>
 6 using namespace std;
 7 const int maxn=1000005;
 8 const int INF=0x3f3f3f3f;
 9 const int mod=998244353;
10 char str[10005][105],s[105];
11 int w[10005];
12 
13 int getminmax(char *word)
14 {
15     int i=0,j=1,k=0;
16     int len=strlen(word);
17     while(i<len && j<len && k<len)
18     {
19         int t=word[(i+k)%len]-word[(j+k)%len];
20         if(!t) k++;
21         else
22         {
23             if(t>0) i=i+k+1;
24             else j=j+k+1;
25             if(i==j) j++;
26             k=0;
27         }
28     }
29     return i<j?i:j;
30 }
31 int main()
32 {
33     set<string>ss;
34     int n;
35     while(~scanf("%d",&n))
36     {
37         for(int i=1;i<=n;++i)
38         {
39             scanf("%s",str[i]);
40             w[i]=getminmax(str[i]);
41             int q=strlen(str[i]);
42             int e=0;
43             for(int j=w[i];j<q;++j)
44                 s[e++]=str[i][j];
45             for(int j=0;j<w[i];++j)
46                 s[e++]=str[i][j];
47             strcpy(str[i],s);
48         }
49         for(int i=1;i<=n;++i)
50         {
51             ss.insert(str[i]);
52         }
53         printf("%d
",ss.size());
54         ss.clear();
55     }
56     return 0;
57 }

View Code