循环滚动字符串的几种方法

题目

例有字符串“abcdefg”，令其向右循环滚动3个字符，则会得到“efgabcd”现给定字符串和滚动字符数，设计一个算法

 

方法一：转变为子问题

例如刚才的题目，我们用(a,b)表示a个字符中滚动b次abcdefg  可以用(7,3)表示，令左边3个字符和右边3个字符交换位置，得到efg(dabc) 其中前3个字符位置已经正确，题目变为(4,3)，同理得到efg(cab)d 题目变为(3,2)，同理得到efg(ba)cd 题目变为(2,1)，同理得到efgabcd，即所求

 

实现代码

void RightShift( char* p, int n ) { int len = strlen(p); n %= len; int flag = 1; while( n * 2 != len ) { if( n > len / 2 ) { n = len - n; flag = 1 - flag; } for( int i = 0; i < n; i++ ) swap( *(p + i), *(p + len - n + i) ); if( flag ) p += n; len -= n; n = min( len, n ); } for( int i = 0; i < n; i++ ) swap( *(p + i), *(p + len - n + i) ); } 

 

方法二：常见方法，不解释具体可参见_JULY_大神的文章http://blog.csdn.net/v_JULY_v/archive/2011/04/14/6322882.aspx上的思路1

 

实现代码

void RightShift( char* p, int n ) { int len = strlen(p); n %= len; { char* b = p; char* e = p + len - n - 1; while( b < e ) swap( *(b++), *(e--) ); } { char* b = p + len - n; char* e = p + len - 1; while( b < e ) swap( *(b++), *(e--) ); } { char* b = p; char* e = p + len - 1; while( b < e ) swap( *(b++), *(e--) ); } }  

 

方法三：交换法

 

此方法是不停用第一个元素和第i个元素进行交换，一共交换len次，就得所求其中i为 0, n % len, 2n % len, 3n % len ... (n-1)*len % len如abcdefg a<->adbcaefg a<->dgbcaefd d<->gcbgaefd g<->cfbgaecd c<->fbfgaecd f<->befgabcd b<->e

 

有一个问题是，如果 n与len非互素，则它们的最大公约数为一组的个数，把整个串分为len/gcd(len,n)组，执行上面的算法

实现代码

int gcd( int a, int b ) { if( b == 0 ) return a; if( b > a ) swap( a, b ); return gcd( b, a % b ); } void RightShift( char* p, int n ) { int len = strlen(p); int seclen = gcd( len, n ); len /= seclen; n /= seclen; for( int j = 0, i = 0; j < len; j++ ) { char* e = p + seclen * i; for( int k = 0; k < seclen; k++ ) { swap( *(p + k), *(e + k) ); } i = ( i + n ) % len; } }