hillbig / esaxx Goto Github PK

ESA can be represented by a BP representation. 
An internal node information can be replaced by a rank operation on BP. 

First, build a permutated hight array from SA directly, which is 2n bits of 
space, and then use this to compute BP. Since currently nodes are enumerated 
in post order, we need to convert this into the BP; that is pre-order

■What steps will reproduce the problem?
1. waf configure && waf
   (enumSubstring.cpp needs to be modified so that it includes <cstdio>.)
2. bin/default/enum_substring < test_ababbab.dat
   The file "test_ababbab.dat" contains a string "ababbab".
3. enum_substring outputs the following results:

        % esaxx-0.0.2/bin/default/enum_substring < test_ababbab.dat
            n:7
        alpha:256
         node:3
        0       3       2       ab
        1       2       3       bab
        2       7       1       a

   Because there are no branch after 'a', i.e. the input does not contain "aa",
   a substring "a" shouldn't appear on the output.


■What is the expected output? What do you see instead?
esaxx-0.0.1 seems to produce a right result.

    % esaxx-0.0.1/bin/default/enum_substring < test_ababbab.dat
        n:7
    alpha:256
     node:4
    0       3       2       ab
    1       2       3       bab
    2       4       1       b
    3       7       0


■What version of the product are you using? On what operating system?
esaxx-0.0.2
Gentoo Linux
gcc-4.6.3


■Please provide any additional information below.

        for (int j = 0; j < len; ++i){ // not ++i but ++j 
            cout << T[beg + j];
        }

■What steps will reproduce the problem?
1. waf configure && waf
   (in fact, I needed to modify enumSubstring.cpp to include <cstdio>.)
2. bin/default/enum_substring < test_abracadabra.dat
3. enum_substring outputs the following results:

    % bin/default/enum_substring < test_abracadabra.dat
        n:11
    alpha:256
     node:5
    0       2       1       a
    1       3       1       a
    2       2       3       bra
    3       2       2       ra
    4       11      0


■What is the expected output? What do you see instead?
Its previous version 0.0.2 has no problem.

    % esaxx-0.0.2/bin/default/enum_substring < test_abracadabra.dat
        n:11
    alpha:256
     node:5
    0       2       4       abra
    1       5       1       a
    2       2       3       bra
    3       2       2       ra
    4       11      0


■What version of the product are you using? On what operating system?
esaxx-0.0.3
Gentoo Linux
gcc-4.6.3


■Please provide any additional information below.
The program works well with a string "mississippi".
Both version 0.02 and 0.03 result in the same output.

    % esaxx-0.0.3/bin/default/enum_substring < test_mississippi.dat
        n:11
    alpha:256
     node:7
    0       2       4       issi
    1       4       1       i
    2       2       1       p
    3       2       2       si
    4       2       3       ssi
    5       4       1       s
    6       11      0

    % esaxx-0.0.2/bin/default/enum_substring < test_mississippi.dat
        n:11
    alpha:256
     node:7
    0       2       4       issi
    1       4       1       i
    2       2       1       p
    3       2       2       si
    4       2       3       ssi
    5       4       1       s
    6       11      0