滴水穿石

海纳百川，有容乃大；壁立千仞，无欲则刚

字符串循环移位

问题描述

将一个n元一维向量向左循环移位k个位置。例如，n=9，k=3， 向量abcdefghi就变成了defghiabc，在考虑到节省内存的情况下，如何在O(n)的复杂度下对向量进行移位。

方法一

移动c = x[0], x[0] = x[k], x[k] = x[2*k], ...依次类推，直到返回到x[0]，改为从c取值。

shift_zaji.c fist algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int gcd(int a, int b)
{
        int r;
        while(1){
                r = a % b;
                if ( r == 0 )
                        return b;
                a = b;
                b = r;
        }
}
void shift(char * str, int n, int k)
{
        int turns = gcd(n, k);
        int i, j, tmp;
        char c;
        k = k % n;
        for( i= 0; i < turns; ++ i){
                c = str[i];
                tmp = i;
                while (1){
                        j = tmp + k;
                        if ( j >= n )
                                j -= n;
                        if ( j == i )
                                break;
                        str[tmp] =  str[j];
                        tmp = j;
                }
                str[tmp] = c;
        }
}

方法二 块交换算法

对向量进行循环移位其实是交换向量ab的两个部分，得到向量ba,如果a代表向量的前k个元素,分为两种情况，

  • length(a) < length(b)那么将b分为blbr, 其中br与a等长，那么将a与br进行交换，最后形成brbla,现在只要交换brbl的子问题。
  • length(a) >= length(b)那么将a分为alar, 其中al与b等长，那么将al与b进行交换，最后形成baral,现在只要交换aral的子问题。
shift_block_swap.c block swap algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

void swap(char * str, int a_l, int b_l, int len)
{
        int i = a_l , j = b_l, k;
        for( k = 0; k < len; k ++){
                str[a_l + k] ^= str[b_l + k];
                str[b_l + k] ^= str[a_l + k];
                str[a_l + k] ^= str[b_l + k];
        }
}
void shift(char * str, int n, int k)
{
        int i = k;
        int p = k;
        int j = n - p;
        while ( i != j){
                if( i > j ){
                        swap(str, p - i , p, j);
                        i -= j;
                }else {
                        swap(str, p - i, p + j - i, i);
                        j = j - i;
                }
        }
        swap(str, p - i, p, j);
}

方法三 求逆算法

同方法二，将问题归结为ab转化为ba，先对a求逆得ar,对b求逆得到br，对arbr逆得ba，就是所求的结果

shift_reverse.c reverse algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void reverse(char * str, int start, int end)
{
        while( start <  end ){
                str[start] ^= str[end];
                str[end] ^= str[start];
                str[start] ^= str[end];
                start ++;
                end --;
        }
}
void shift(char * str, int n, int k)
{
        k = k % n;
        reverse(str, 0, k - 1);
        reverse(str, k, n - 1);
        reverse(str, 0, n - 1);
}