CODEWITHSUNDEEP
javaalgorithmsuffix-treesuffix-arraylongest-substring
hackerspark
hackerspark

Reputation: 11

Suffix array/suffix tree with numbers

Can suffix trees or suffix arrays be used effectively with numbers?

For example:

Can it be used with the array [1,2,3,4,5,3,9,8,5,3,9,8,6,4,5,3,9,11,9,8,7,11] to extract all possible non-overlapping repeating sub-strings of all sizes from the array's contents? If so, could you provide an implementation for the same. I am trying to achieve the same but haven't reached an effective solution.

Expected results:

4,5
4,5,3
4,5,3,9
5,3
5,3,9
5,3,9,8
...

Considering the array : [1,2,3,4,5,9,3,4,5,9,3,3,4,5,9,3], the non overlapping repeating sequence implies that the extracted group:3,4,5,9,3 is derived from the repetitions starting at indexes 2 to 6 and 11 to 15 and NOT 6 to 10

Upvotes: 0

Views: 366

Answers (1)

RPresle
RPresle

Reputation: 2561

Here it is 

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5, 3, 9, 8, 5, 3, 9, 8, 6, 4, 5, 3, 9, 11, 9, 8, 7, 11}; // expect : 2,3  /  2,3,4  /  3,4
    Set<String> strings = new HashSet<>();
    // for every position in the array:
    for (int startPos = 0; startPos < arr.length; startPos++) {

        // from the actual position + 1 to the end of the array
        for (int startComp = startPos + 1; startComp < arr.length; startComp++) {
            int len = 0; // length of the sequence
            String sum = "";
            // while not at the end of the array, we compare two by two
            while (startComp + len < arr.length && arr[startPos + len] == arr[startComp + len]) {
                sum += arr[startPos + len];
                // if detected sequence long enough
                if (len > 0) {
                    strings.add(sum);
                }
                len++;
            }
            // just to gain some loop
            startComp = startComp + len;
        }
    }
}

For your data, my results are :

98 453 4539 45 5398 539 398 53 39

Basically, loop through your array. Foreach letter compare to every letter to its right. If you find the same letter then compare the growing sequence and add it to the set if its length>1.

Hope it helps

Upvotes: 1

Related Questions