Получить все подстроки, которые являются уникальными

Question

Я работаю над программой, которая вычисляет все возможные различные непрерывные подстроки заданной входной строки.

Вот моя программа:

public int getAllUniqueSubset(String str) {
        Set<String> set = new HashSet<String>();
        for (int i = 0; i < str.length(); i++) {
            for (int j = 0; j < str.length() - i; j++) {
                String elem = str.substring(j, j + (i+1));
                if (!set.contains(elem)) {
                    set.add(elem);
                }
            }
        }
        return set.size();
    }

Теперь, когда я использовал это во время онлайн экзамен несколько дней назад, он провалился с ошибками тайм-аута, так как длина входной строки может быть до 10 степени 5.

Также аналогичный вопрос задается в этом посте - поиск всех различных подстрок строки также я использовал тот же ответ.

Как правильно решить эту программу?

Answer 1

Длина строки 10 ^ 5 предполагает, что квадратичное c решение слишком медленное. Вы генерируете все n ^ 2 подстрок, а также вычисляете их хэши, поэтому общее время равно cubi c и ожидаемое время ожидания.

Вместо этого вы можете построить массив суффиксов за O (nlogn), а затем построить LCP (самый длинный общий префикс) с помощью метода Kasai или другого al go.

Мы можем видеть, что каждый суффикс p[i] имеет длину n - p[i] и создает n - p[i] префиксов в качестве подстрок. Но lcp[i-1] префиксы совпадают с префиксами предыдущего суффикса! Таким образом, у нас есть только n - p[i] - lcp[i-1] новых подстрок inique для каждого суффикса. Go через siffixes и получить количество различных подстрок в O (n) времени.

Общее время

O(nlogn) (suffix array) + 
O(n) (Kasai LCP) + 
O(n) for counting = 
   O(nlogn)

Answer 2

Попробуйте это решение от GeeksForGeeks

public class GFG { 
    Set<String> set = new HashSet<String>();
    public static void SubString(String str, int n) 
    { 
        for (int i = 0; i < n; i++)  
            for (int j = i+1; j <= n; j++) 
                set.add(str.substring(i, j)); 
    } 

    public static void main(String[] args) 
    { 
        String str = "abcd"; 
        SubString(str, str.length()); 
    } 
} 

Answer 3

Некоторые мысли, которых может быть недостаточно для решения проблемы масштабируемости:

1. Вам не нужна проверка if (!set.contains(elem)), так как она уже используется в методе set.add() логи c. Требуется некоторое время, чтобы проверить это (даже постоянное).

2. Возможно, вы захотите изменить Set to List (даже если это связано с большим потреблением пространства) и преобразовать в set в конце, чтобы удалить дубликаты.

3. Кажется, что некоторые вычисления можно выполнять параллельно (например, назначить работнику выполнять подстроки длины 1, другой - длину 2, и т. Д. c). Их не нужно будет перепроверять (т. Е. Результаты каждого работника не нужно проверять на дубликаты). Например, вы можете попробовать многопоточность или Spark (если издержки распараллеливания не больше).