題目大意：
給出一個01字符串。將其循環(huán)移位，將所有移位后的串列舉出來，并按字典序排序。
比如“abcd”，可以移位成“bcda”，“cdab”，“dabc”。排序以后，為
“abcd”
“bcda”
“cdab”
“dabc”
將最后一列的字母抽取出來，即“dabc”。
然后，讓你還原出第一行的字符。
這是一個看上去很蛋疼的問題，沒事研究這個干啥呢。
想了半天，做不出來。看到discuss里面有人給了一個鏈接：
http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform發(fā)現(xiàn)居然是一個壓縮算法！
據(jù)說，將最后一列抽取出來，較原字符串相比，能夠
“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
還是復(fù)雜度很高，為 O(N*N*lgN)。
那disscus里面說的O(N)的方法和那么多0ms是咋來的呢？
想了一下。發(fā)現(xiàn)每一次添加列然后再排序的操作，都是做一樣的置換。
因為每次添加的列都一樣，排序的結(jié)果當(dāng)然也是一樣（比如是穩(wěn)定排序）。
所以，第i列的結(jié)果就是置換i次的結(jié)果。我們只需要第一行的數(shù)據(jù)。
經(jīng)過一次排序之后，就知道每一個行置到了哪個地方，如果第三行到了第一行，第五行到了第三行。
那么：
第一列第一行的就是未排序數(shù)據(jù)的第三行
第二列第一行的就是未排序數(shù)據(jù)的第五行
由于數(shù)據(jù)中只有01，完全可以在O(N)內(nèi)完成排序操作，之后得出第一行的操作也是 O(N) 完成的。
可惜代碼實現(xià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;
}