[ UVA ] 741 - Burrows Wheeler Decoder

題目:
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=682

解法:
BWT逆轉換，可以參考Morris的這篇，透過觀察題目範例:

1. A B A N A N
2. A N A B A N
3. A N A N A B
4. B A N A N A
5. N A B A N A
6. N A N A B A
(我們只知道最後一行(設為字串s)的NNBAAA和原字串在第4個位置)

發現我們只能利用排序求出第一行的AAABNN，因為BWT轉換是利用字串rotate，所以可以把s和它結合起來
NA
NA
BA
AB
AN
AN
在排序就可以得到前兩行了
AB
AN
AN
BA
NA
AN
同樣發現因為rotate的關係，所以可以再開頭加上s求出前三行.....以此類推

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

#include<bits/stdc++.h> using namespace std; int main(){ bool is=0; string s; for(int p;cin>>s>>p;){ if(s=="END")break; if(is)cout<<endl; is=1; int n=s.length(); string a[n]; for(int i=0;i<n;++i){ for(int j=0;j<n;++j)a[j]=s[j]+a[j]; sort(a,a+n); } cout<<a[p-1]<<endl; } return 0; }