UVa1584 - Circular Sequence

  

   

    

     

    
    

     

      //UVa1584 - Circular Sequence
     
    
   

    

     

    
    

     

      //题目:给你一个环状串，输出它以某一位置为起点时得到最小字典序的串。
     
    
   

    

     

    
    

     

      //分析:从初位置到末位置每次更新字典序较小的起始位置
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #define max 105
     
    
   

    

     

    
    

     

      //对于序列s，i是否比ans小
     
    
   

    

     

    
    

     

      int find(char* s, int x, int y){
     
    
   

    

     

    
    

     
	int len = strlen(s);
     
    
   

    

     

    
    

     
	//字典序比较:直接比较从第i个起的不相等的较小字符即为字符串较小字典序(//长度不等时较短的就较小)
     
    
   

    

     

    
    

     
	for(int i = 0; i < len; i++){
     
    
   

    

     

    
    

     
		if(s[(x+i)%len] != s[(y+i)%len])
     
    
   

    

     

    
    

     
			return s[(x+i)%len] < s[(y+i)%len];
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;//相等
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	int T;
     
    
   

    

     

    
    

     
	char s[max];	
     
    
   

    

     

    
    

     
	scanf("%d",&T);
     
    
   

    

     

    
    

     
	while(T--){
     
    
   

    

     

    
    

     
		scanf("%s",s);
     
    
   

    

     

    
    

     
		int ans = 0;
     
    
   

    

     

    
    

     
		int len = strlen(s);
     
    
   

    

     

    
    

     
		for(int i = 1; i < len; i++){
     
    
   

    

     

    
    

     
			if(find(s, i, ans)) ans = i;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//***输出,用取模的方法来实现,从尾到头相连接的环装输出
     
    
   

    

     

    
    

     
		for(int i = 0; i < len; i++)
     
    
   

    

     

    
    

     
			putchar(s[(i+ans)%len]);
     
    
   

    

     

    
    

     
		putchar('\n');
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      /*
     
    
   

    

     

    
    

     

      *DATE IN:
     
    
   

    

     

    
    

     

      2
     
    
   

    

     

    
    

     

      CGAGTCAGCT
     
    
   

    

     

    
    

     

      CTCC
     
    
   

    

     

    
    

     

      
     
    
   

    

     

    
    

     

      *DATE OUT:
     
    
   

    

     

    
    

     

      AGCTCGAGTC
     
    
   

    

     

    
    

     

      CCCT
     
    
   

    

     

    
    

     

      */
     
    
  
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/54838467