字符串之旋转

一、原理
        把字符串前面的若干字符移动到字符串的尾部，比如：把字符串"abcdef"前2位字符移动到后面得到字符串为“cdefab”。
        可以把字符串看成两段，分别即为XY，左旋转相当于把字符串XY变成YX。先从数学的角度来分析一下翻转操作吧：
        把X翻转后记为X^T，则(X^T)^T=X，首先对X和Y分别进行翻转操作得到X^TY^T，再对X^TY^T进行翻转操作得到XY，即(X^TY^T)^T=(Y^T)^T(X^T)^T=YX，至此翻转完成。

二、实现
        根据前面原理，可以将字符串分为两段，第一段为前m个字符，其余字符分到第二段，定义一个翻转函数，然后分三步走，即先翻转第一段，再翻转第二段，最后将翻转后的两段合在一起翻转一次即可。这样时间复杂度为O(n)。
        #include  

        char* rotate(char *array,     // 待旋转字符串
                        int begin,          // 旋转起点
                        int end)            // 旋转终点
        {  
            while ((NULL != array) && (begin < end)) 
            {  
                char temp = array[begin];  
                array[begin] = array[end];  
                array[end] = temp;  
                begin++;  
                end--;  
            }  

            return array;
        }  
      
        char* LeftRotate(char *array, int number) 
        {  
            if (NULL == array)
            {
                return NULL;
            }

            char *temp = array;
            int len = 0;
            while (*temp++)
            {
                ++len;
            }

            // X^T  
            rotate(array, 0, number-1);  
            // Y^T  
            rotate(array, number, len-1);  
            // (X^TY^T)^T  
            rotate(array, 0, len-1); 

            return array;
        }      

        int main()
        {
            char array[] = "abcdef";
            int number = 2;  
            printf("str=%s-->LeftRotate=%s\n", array, LeftRotate(array, number));

            return 0;
        }