Who can give me some hint ?

it's a linear algorithm, although classic I think. You can search the web for Burrows Wheeler algorithm, that's it's name. The solution is something like this: the first column contains the letters sorted. You have the last one (column). You start from the given position (line) in the first column. you see the element in the last one and also it's counter from its type: example: if it is an 'a' and in the last column, upwards, it was another 'a', than its id is 2. Now you go to the position in the first column for this 'a', the second. And so on...

 input_seq----sorted_seq
 1---------------10
 2----------------9
 3>>start1-------1
 4---------------11-<<match3-"abr"
 5---------------8
 6---------------2
 7>>start2------3<<--match1-"a"
 8---------------4
 9---------------5
 10--------------6
 11>>start3-----7-<<-match2-"ab"


and so on.



Edited by author 19.04.2004 02:16

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