本文主要是介绍Vision_字符串_最小（大）表示法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
///定义：/*
求解问题：n个字符串围成一个环，请从这个环中找出字典序最大（或最小）的
长度为n的字符串（下标尽可能小）
*/
///代码：
/*
**name:最小表示法
**function:求解循环字符串的最小字典序串
**输入参数：字符串+字符串长度
**输出参数：从某下标开始所得到的串字典序最小&&下标最小
**复杂度：O（n）
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int MINR(char s[],int l){ //s是原串（未加倍过），l是原串长for(int i=0;i<l;++i)s[l+i]=s[i]; //将s串加倍s[2*l]=0;int i=0,j=1; //利用i，j指针移动while(i<l&&j<l){int k=0;while(s[i+k]==s[j+k]&&k<l)++k; //不断比较直到比较完长度为l的串或两个子串不相等if(k==l)return min(i,j); //若比较出长度为l则直接返回靠前的那个串的开始位置if(s[i+k]>s[j+k])i=max(i+k+1,j+1); //i串比j串大，那么i到i+k中的串都比j串大，i可以直接//移动到i+k+1位置，而起始位置比j小的肯定都在j移动过程中比较过，//所以i可以直接移动到j+1位置，因此取这两值的最大值else j=max(j+k+1,i+1); //同上}return min(i,j); //返回位置靠前的下标
}
int main(){char *s;MINR(s,strlen(s));return 0;
}
/*
**name:最大表示法
**function:求解循环字符串的最大字典序串
**输入参数：字符串+字符串长度
**输出参数：从某下标开始所得到的串字典序最大&&下标最小
**复杂度：O（n）
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int MAXR(char s[],int l){for(int i=0;i<l;++i)s[l+i]=s[i];s[2*l]=0;int i=0,j=1;while(i<l&&j<l){int k=0;while(s[i+k]==s[j+k]&&k<l)++k;if(k==l)return min(i,j);if(s[i+k]<s[j+k])i=max(i+k+1,j+1);else j=max(j+k+1,i+1);}return min(i,j);}int main(){char *s;MAXR(s,strlen(s));return 0；}///扩展：
/*
求最大表示法步骤：
①初始化i=1,j=2,len为字符环长度
②从k=0开始，检验str[i+k]与str[j+k]对应的字符是否相等，如果相等则k++，一直下去，
如果k<len时找到了第一个不同，执行步骤③，如果k==len，执行步骤④
③若s[i+k]>s[j+k]，则i滑动到i+k+1处，否则j滑动到j+k+1处，若移动完后i==j，则j++，
继续执行步骤②，如果i或j有一个超过len，执行步骤④
④返回i和j小的那个，就是答案
技巧：将字符串完全复制一遍接在原字符串的后面，就可以模拟出一个环
*/
这篇关于Vision_字符串_最小（大）表示法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
