字符串最大最小表示法（hdu 3374）

深藏阁楼爱情的钟 2023-06-01 06:12 26阅读 0赞

# 字符串最大最小表示法 #

[出处][Link 1]

题目：输出最大最小表示是从哪一位开始，而且输出数量

[hdu3374 String Problem][]

数量好求，肯定是字符串的循环节，循环节可以直接通过KMP的Next数组得到。

对于最大最小表示法，就是将字符串不断旋转，得到字典序最大或者最小的。

求字符串最小表示的方法

1.  利用两个指针 **p1** , **p2** 。初始化时p1指向 **s\[0\]**, **p2** 指向 **s\[1\]** 。

2.  k = 0开始，检验 **s\[p1+k\]** 与 **s\[p2+k\]** 对应的字符是否相等，如果相等则k++，一直下去，直到找到第一个不同，(若k试了一个字符串的长度也没找到不同，则那个位置就是最小表示位置，算法终止并返回)。则该过程中，**s\[p1+k\]** 与 **s\[p2+k\]** 的大小关系，有三种情况：

*  (A). **s\[p1+k\] > s\[p2+k\]** ，则 **p1** 滑动到 **p1+k+1** 处 --- 即\* \*s1\[p1->p1+k\]\*\*不会

是该循环字符串的“最小表示”的前缀。 k置为0

*  (B). **s\[p1+k\] < s\[p2+k\]** ，则p2滑动到 **p2+k+1** 处， k置为0

*  (C). **s\[p1+k\] = s\[p2+k\]** ，则 **k++； if (k == len)** 返回结果。

注:这里滑动方式有个小细节，若滑动后 **p1 == p2** ，将正在变化的那个指针再+1。直到p1、p2把整个字符串都检验完毕，返回两者中小于 len 的值。

1.  如果 **k == len** ， 则返回p1与p2中的最小值

其实最大表示法一样，大小于的时候改变一下就照了，可以写在一个函数里面。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAX=1000000+10; char str[MAX]; int nex[MAX]; /* 比找最小表示法，相当于找着一个字符串a，再找一个一直循环比较 如果他是最小的，就会一直增加比较，直到长度为len则返回 如果出现i和j相等的情况，j加1最后返回小的那一个就行 */ void Get_nex(int len){ int i=0,j=-1; nex[0]=-1; while(str[i]){ if(j==-1||str[i]==str[j]){ i++;j++; nex[i]=j; }else j=nex[j]; } } int min_max_express(char *s,int len,bool flag){//最小表示法和最大表示法写到一块儿了 int i=0,j=1,k=0; while(i<len&&j<len&&k<len){//一次就能够找着 int t=s[(j+k)%len]-s[(i+k)%len];//比较两个字符 if(t==0)k++;//相等，就后移比较下一个字符 else{ if(flag){//最小表示法 if(t>0)j+=k+1; //+(k+1)相当于直接把相等的跳过 else i+=k+1; }else{//最大表示法 if(t<0) j+=k+1; else i+=k+1; } if(i==j)j++; k=0; } } return min(i,j); } int main(){ while(scanf("%s",str)!=EOF){ int len=strlen(str); int min_express=min_max_express(str,len,true); int max_express=min_max_express(str,len,false); Get_nex(len); int ans=len%(len-nex[len])?1:len/(len-nex[len]); printf("%d %d %d %d\n",min_express+1,ans,max_express+1,ans);//因为从0开始的，最大最小项+1 } return 0; }

转载于:https://www.cnblogs.com/tttfu/p/11313599.html

[Link 1]: http://blog.csdn.net/acm_cxlove/article/details/7854526
[hdu3374 String Problem]: http://acm.hdu.edu.cn/showproblem.php?pid=3374