如何理解字符串的最大、最小表示法

拼搏现实的明天。 2023-05-22 04:46 19阅读 0赞

## 一、什么是循环字符串的最小表示法 ##

**对于一个字符串S，求S的循环的同构字符串S’中字典序最小的一个。**  
如：S=bacd，则S’可以是acdb,cdba,dbac，其中最小表示的S’是acdb。即该字符串的循环同构字符串中字典序最小的一个是acdb

## 二、如何求解一个字符串的循环同构的最小表示 ##

**求解这个问题，实质上是在S串中寻找一个位置，从该位置起循环输出S，此时得到的S’字典序是最小的**

**思路一：**  
首先我们比较容易想得到的一个思路就是：设置i和j两个指针，i指向最小表示的位置，j指向比较指针。

令i=0,j=1,则
    若s[i]>s[j],则当前i指向的位置一定不是最小表示的起点位置，修改i的值，i=j,j++;
    若s[i]<s[j]，则当前j指向的位置不是最小表示的起点位置，修改j的值继续进行比较，j++;
    若s[i]=s[j],说明当前i和j指向的位置开头的字符串的头是相同的，需要接着比较以该位置开头的字符串接下来位置的大小。故此时
               设指针k=1,分别从i和j位置开始向下进行比较，若s[i+k]=s[j+k],则k++，即需要继续向下进行比较
               若s[i+k]<s[j+k],说明由i位置开头的字符串小于由j位置开头的字符串，故i的值不变，j++，进行继续比较
               若s[i+k]>s[j+k]，说明由i位置开头的字符串并不是最小表示，j位置开头的字符串小于i位置开头的字符串，修改i的值，i=j,j++;
    最后返回i所指向的位置，即为最小表示的位置。

可以看出以上方式在遇到类似bbbbbbba这样的字符串时，i指针每次移动一位，时间复杂度较高。

**思路二、**

同样令i=0,j=1，此时维护i和j两个指针，且i不一定指向最小位置，i和j都是指向可能的最小位置。
    若s[i]>s[j]时，i=j,j++;
    若s[i]<s[j]时，j++;
    若s[i]==s[j]时，设指针k,分别从i和j的位置开始向下比较
    				当s[i+k]=s[j+k]，k++;
    				当s[i+k]<s[j+k]时，此时说明j不是最小表示，移动j,j=j+k+1;
                    当s[i+k]>s[j+k]时，此时说明i不是最小表示，移动i,i=i+k+1;
    最后返回i和j中最小的值即为最小表示的位置

对于当**s\[i+k\]<s\[j+k\]时，此时说明j不是最小表示，移动j,j=j+k+1;**  
因为当s\[i+k\]<s\[j+k\]，即第i+k个位置的字母序小于第j+k位置的字母序，因为此时从j位置开始（不包括j)到j+k位置的任何一个以这之间位置开头的字符串都将大于i位置开头的字符串。  
![lz][]

## 三、代码实现 ##

**字符串的最小表示法**

//字符串的最小表示法
    #include<iostream>
    #include<string>
    using namespace std;
    int main(){
        
    	string str;
    	while(cin>>str){
        
    		int i=0,j=1,k=0;
    		int len=str.size();
    		while(i<len&&j<len&&k<len){
        
    			//str[i+k]与str[j+k]依次进行比较 
    			int t=str[(i+k)%len]-str[(j+k)%len];
    			//相等的情况下，k++ 
    			if(t==0){
        
    				k++;
    			}
    			else{
        
    				if(t>0){
        
    					i=i+k+1;
    				}
    				else{
        
    					j=j+k+1;
    				}
    				if(i==j){
        
    					j++;
    				}
    				k=0;
    			}
    		}
    		//min即为最小字符串表示的下标 
    		int min=i<j?i:j;
    		//还原出最小字符串表示 
    		string s=str.substr(min,len-min)+str.substr(0,min);
    		cout<<s<<endl; 
    	}
    	return 0;
    }

**字符串的最大表示法**

//字符串的最大表示法
    #include<iostream>
    #include<string>
    using namespace std;
    int main(){
        
    	string str;
    	while(cin>>str){
        
    		int i=0,j=1,k=0;
    		int len=str.size();
    		while(i<len&&j<len&&k<len){
        
    			int t=str[(i+k)%len]-str[(j+k)%len];
    			if(t==0){
        
    				k++;
    			}
    			else{
        
    				//说明str[i+k]>str[j+k],当前j开头的字符串不是最大表示，要移动j 
    				if(t>0){
        
    					j=j+k+1;
    				}
    			    //说明str[i+k]<str[j+k],当前i开头的字符串不是最大表示，要移动i
    				else{
        
    					i=i+k+1;
    				}
    				//若移动之后i和j相等，此时将j++，继续进行比较 
    				if(i==j){
        
    					j++;
    				}
    				k=0;
    			}
    		}
    		//返回i和j中小的那个值 
    		int max=i<j?i:j;
    		string s=str.substr(max,len-max)+str.substr(0,max);
    		cout<<s<<endl; 
    	}
    	return 0;
    }

[lz]: /images/20230521/9a06c47c4cc94a9c8ef3aae2e68a04b8.png