题目大意：
给出一个01字符串。将其循环移位，将所有移位后的串列举出来，并按字典序排序。
比如“abcd”，可以移位成“bcda”，“cdab”，“dabc”。排序以后，为
“abcd”
“bcda”
“cdab”
“dabc”
将最后一列的字母抽取出来，即“dabc”。
然后，让你还原出第一行的字符。
这是一个看上去很蛋疼的问题，没事研究这个干啥呢。
想了半天，做不出来。看到discuss里面有人给了一个链接：
http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform发现居然是一个压缩算法！
据说，将最后一列抽取出来，较原字符串相比，能够
“easy to compress a string that has runs of repeated characters by techniques such as
move-to-front transform and
run-length encoding.”
这个就不理解了。。
这题简化了一下条件，字符串只包含01。
看了它的还原方法。如果直接这样写：
def ibwt(r):
"""Apply inverse Burrow-Wheeler transform."""
table = [""] * len(r) # Make empty table
for i in range(len(r)):
table = [r[i] + table[i] for i in range(len(r))] # Add a column of r
table.sort()
s = [row for row in table if row.endswith("\0")][0] # Find the correct row (ending in "\0")
return s.strip("\0") # Get rid of trailing null character
还是复杂度很高，为 O(N*N*lgN)。
那disscus里面说的O(N)的方法和那么多0ms是咋来的呢？
想了一下。发现每一次添加列然后再排序的操作，都是做一样的置换。
因为每次添加的列都一样，排序的结果当然也是一样（比如是稳定排序）。
所以，第i列的结果就是置换i次的结果。我们只需要第一行的数据。
经过一次排序之后，就知道每一个行置到了哪个地方，如果第三行到了第一行，第五行到了第三行。
那么：
第一列第一行的就是未排序数据的第三行
第二列第一行的就是未排序数据的第五行
由于数据中只有01，完全可以在O(N)内完成排序操作，之后得出第一行的操作也是 O(N) 完成的。
可惜代码实现出来，也没有到 0ms ，好像是 79ms 。代码写得烂！高手改改也是0ms了。
代码里也包括了一个求普通字符串的BWT操作。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp(const void *a, const void *b)
{
return strcmp(*(char **)a, *(char **)b);
}
void bwt(char *in, char *out)
{
static char arr[32][32], *sorted[32];
int len, i, j;
len = strlen(in);
for (i = 0; i < len; i++) {
sorted[i] = arr[i];
for (j = 0; j < len; j++)
sorted[i][j] = in[(i + j) % len];
sorted[i][len] = 0;
}
qsort(sorted, len, sizeof(sorted[0]), cmp);
for (i = 0; i < len; i++)
printf("%s\n", sorted[i]);
for (i = 0; i < len; i++)
out[i] = sorted[i][len - 1];
out[i] = 0;
}
int cmp2(const void *a, const void *b)
{
if (*(int *)a == *(int *)b)
return *((int *)a + 1) - *((int *)b + 1);
else
return *(int *)a - *(int *)b;
}
void ibwt(char *in, char *out)
{
struct {
int ch, idx;
} arr[32];
int i, len, j;
len = strlen(in);
for (i = 0; i < len; i++) {
arr[i].ch = in[i];
arr[i].idx = i;
}
qsort(arr, len, sizeof(arr[0]), cmp2);
for (i = 0; i < len; i++)
printf("%c %d\n", arr[i].ch, arr[i].idx);
j = arr[0].idx;
for (i = 0; i < len - 1; i++) {
out[i] = in[j];
j = arr[j].idx;
}
out[len - 1] = in[0];
out[len] = 0;
printf("%s\n", out);
}
void test()
{
char in[32], out[32], res[32];
strcpy(in, "banana");
bwt(in, out);
printf("out:\n%s\n", out);
ibwt(out, res);
}
int main()
{
static int map[3032], arr[3032], n, val, one[3032], one_cnt, zero_cnt, i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &val);
arr[i] = val;
if (val)
one[one_cnt++] = i;
else
map[zero_cnt++] = i;
}
for (i = 0; i < one_cnt; i++)
map[zero_cnt + i] = one[i];
val = map[0];
for (i = 0; i < n - 1; i++) {
printf("%d ", arr[val]);
val = map[val];
}
printf("%d\n", arr[0]);
return 0;
}