Суффиксный массив / суффиксное дерево с числами

Question

Могут ли суффиксные деревья или суффиксные массивы эффективно использоваться с числами?

Например:

Можно ли использовать с массивом [1,2,3,4,5,3,9,8,5,3,9,8,6,4,5,3,9,11,9,8,7,11] извлечь все возможные непересекающиеся повторяющиеся подстроки всех размеров из содержимого массива? Если да, не могли бы вы предоставить реализацию для того же. Я пытаюсь достичь того же, но не нашел эффективного решения.

Ожидаемые результаты:

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

---

Учитывая массив: [1,2,3,4,5,9,3,4,5,9,3,3,4,5,9,3]неперекрывающаяся повторяющаяся последовательность подразумевает, что извлеченная группа:3,4,5,9,3 получается из повторений, начиная с индексов 2-6 и 11-15, а НЕ 6-10

Answer 1

Вот

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;
        }
    }
}

Для ваших данных, мои результаты:

98 453 4539 45 5398 539 398 53 39

По сути, цикл через ваш массив. Буква Foreach сравнивается с каждой буквой справа. Если вы найдете ту же букву, сравните растущую последовательность и добавьте ее в набор, если ее длина>1.

Надеюсь, поможет