More About Burrows-Wheels visit
http://www.cs.princeton.edu/courses/archive/spr03/cs226/assignments/burrows.html To this problem, I think the kernel is how to make the next-element array of the INPUT data but not to get the result step by step.
As an example,
0 a a b r a c a d a b r 2
1 a b r a a b r a c a d 5
*2 a b r a c a d a b r a 6
3 a c a d a b r a a b r 7
4 a d a b r a a b r a c 8
5 b r a a b r a c a d a 9
6 b r a c a d a b r a a 10
7 c a d a b r a a b r a 4
8 d a b r a a b r a c a 1
9 r a a b r a c a d a b 0
10 r a c a d a b r a a b 3
To get the no.2 string,and we have got the last column.If we start with this original,the most easy way is to use the squence of the string array:
the end of row 2 = a
next to seek the suffix of 'a' in row 2:
You may sort the whole to form the head of each row.And the head is just the suffix for each end of row.
But if the input is special Your sort program would run out of the time.(Only 1/4 sec)
Changing the way of thinking may useful why not start with prefix.please watch row 0 and row 9, it's easy to find difference. r in 0 row is end but is head in 9 row.
In row 9 the suffix of end 'b' is r,right?
And how about the num of row 9 comes from?
9=3<four as >+2<2 bs>+1<1 c>+1<1 d>+0<0 r before this 'r'>
And the suffix of b is just 'r'<row 0>.
So when construct the next array,input[i],we may proceed as follow:
next[s[i]+p[i]]=i
<s[i] is the array that record the number of sign before each kind of letter appereance in the head in the sorted array (as 4a 2b 1c 1d in example)
p[i] is the array that recored the number of same sign before this sign appreance(as 0 r in example)>
if the data structure is all right, you may be accepted in only 0.04 sec.
Edited by author 20.04.2004 00:39