If you are using sort in your algo and sorting pairs<char ch,int position>, you must compare this pairs by a "ch", but if "ch"`s are equal - you must compare "position". Comparsion function may be like that:

struct s{char c;int p;};

bool cmp(s a, s b)
{
    if(a.c!=b.c)
    {
        return a.c<b.c;
    }
    return a.p<b.p;
}

Use stable_sort instead of sort (if you're doing on C/C++)

there is 32bit Free Pascal Compiler.

var s:string;
begin
  read(s);
 // your code
end.

1
rdarcaaaabb

2
rdarcaaaabb

3
rdarcaaaabb

4
rdarcaaaabb

5
rdarcaaaabb

6
rdarcaaaabb

7
rdarcaaaabb

8
rdarcaaaabb

9
rdarcaaaabb

10
rdarcaaaabb

11
rdarcaaaabb


Answers here

aabracadabr
abraabracad
abracadabra
acadabraabr
adabraabrac
braabracada
bracadabraa
cadabraabra
dabraabraca
raabracadab
racadabraab


Need more?

I found the problem.
It was using 'string' class instead of just char array.
Probably when a string is long (100000 characters) then C++ allocate its memory in chucnks which make its access much more slower (or maybe because some limit checks).

Anyway, when I changes it to char array, it's running time was at least 10 time faster!!!

Test1: a
Test2: a...a (100000 times)
Answers of course are the same.

HERE!!!
const
maxlen=100001;{Maximal message length}
nalfa=256;{Symbols in alphabet}
rasset: set of char=['A'..'Z', '_', 'a'..'z'];
var
countmas: array [#0..#255] of longint;
{Quantity of each char in message, from #0 to #255}
t: array [0..maxlen] of longint;
{Backward vector}
inblock: array [0..maxlen] of char;
{"Encoded" message}
len,{current message length}
posit,{position of initial message in the sorted list}
i,{simple counter}
sum: longint;
ch: char;
begin
readln(posit);
dec(posit);
{===Initializing the arrays and other variables===}
len:=0;
fillchar(countmas, sizeof(countmas), 0);
fillchar(t, sizeof(t), 0);
fillchar(inblock, sizeof(inblock), 0);
{===reading encoded message===}
while (not seekeof) do
begin
read(ch);
inc(len);
inblock[len-1]:=ch;
end;
{===Counting symbols in message===}
for i:=0 to len-1 do
inc(countmas[inblock[i]]);
{===Starting sorting symbols to make backward vector T===}
sum:=0;
for i:=0 to nalfa-1 do
begin
inc(sum, countmas[chr(i)]);
countmas[chr(i)]:=sum-countmas[chr(i)]
end;
{===Calculating backward vector T===}
for i:=0 to len-1 do
begin
t[countmas[inblock[i]]]:=i;
inc(countmas[inblock[i]])
end;
{===Writing out "decoded" (initial) message===}
for i:=0 to len-1 do
begin
posit:=t[posit];
write(inblock[posit])
end
end.

I write: seekeof(not eof) ;~)))

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