Peter_Matthew的博客

最小表示法/最大表示法

2019-02-15

我们可以求出最小/最大开始的位置然后输出。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int getMin(char *s)  
{
int i=1,j=2,k=0;
int len=strlen(s+1);
while(i<=len&&j<=len&&k<len)
{
int t=s[(i+k-1)%len+1]-s[(j+k-1)%len+1];
if(!t)k++;
else
{
if(t>0)i=i+k+1;
else j=j+k+1;
if(i==j)j++;
k=0;
}
}
return min(i,j);
}
int getMax(char *s)
{
int i=1,j=2,k=0;
int len=strlen(s+1);
while(i<=len&&j<=len&&k<len)
{
int t=s[(i+k-1)%len+1]-s[(j+k-1)%len+1];
if(!t)k++;
else
{
if(t>0)j=j+k+1;
else i=i+k+1;
if(i==j)j++;
k=0;
}
}
return min(i,j);
}

下面是一份0下标开始的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int getMin(char *s)  
{
int i=0,j=1,k=0;
int len=strlen(s);
while(i<len&&j<len&&k<len)
{
int t=s[(i+k)%len]-s[(j+k)%len];
if(!t)k++;
else
{
if(t>0)i=i+k+1;
else j=j+k+1;
if(i==j)j++;
k=0;
}
}
return min(i,j);
}
int getMax(char *s)
{
int i=0,j=1,k=0;
int len=strlen(s);
while(i<len&&j<len&&k<len)
{
int t=s[(i+k)%len]-s[(j+k)%len];
if(!t)k++;
else
{
if(t>0)j=j+k+1;
else i=i+k+1;
if(i==j)j++;
k=0;
}
}
return min(i,j);
}


知识共享许可协议

知识共享许可协议

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

标签: 自缚船
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章