Найти суперструну в наборе строк

Question

У меня есть список строк, например:

cargo
cargo pants
cargo pants men buy
cargo pants men
cargo pants men melbourne buy

В этом случае строка, содержащая все оставшиеся строки, cargo pants men melbourne buy. Я хотел бы удалить все более короткие строки и сохранить только самую длинную «суперстроку».

Обратите внимание, что если существует 2 запроса cargo pants и cargo shorts, они будут рассматриваться как 2 разных запроса и выиграны не объединяться.

До сих пор я делал это методом грубой силы - выбирал строку из набора и проходил по тому же набору, удаляя все остальные строки, которые являются «подстроками» текущей строки. Грубо говоря,

for (String p: big_set) {
    for (String q: big_set) {
        if (!p.equals(q)) {
            if (has_all_words(p, q)) { /* If all words in 'p' is also in 'q' */
                big_set.remove(p);
                break;
            }
        }
    }
}

Есть ли интеллектуальный алгоритм, чтобы сделать это менее чем за O (n ^ 2) времени? В этой функции has_all_words будет сохранять порядок слов при сравнении.

Для любопытных у меня есть огромный список из нескольких миллиардов поисковых запросов (например, те, которые отправляются в Google / Yahoo / Bing) и Я пытаюсь найти гипернымы для этих запросов. Есть сервер, который анализирует эту строку и производит различные интересные категории. Я пытаюсь сжать список запросов в надежде минимизировать вычислительные затраты и пропускную способность. Этот метод, безусловно, значительно уменьшает пропускную способность (потому что люди не могут просто думать о buy cargo pants melbourne в одном go), но стоимость предварительного вычисления непомерно высока. И поэтому я охотился за алгоритмами, которые могут это сделать, но я еще не сталкивался ни с чем, что делает это.

Answer 1

• Я думаю, все, что вы хотите попросить, это удалить все те подстроки, которые можно найти в суперстроке. Как и в случае с ["foo bar", "foo baz"] вы придется хранить обе строки.

• Если мое предположение верно, то да, вы можете достичь его менее чем за O (n ^ 2). перед тем, как начать с чего-нибудь короткого, каждую суперструну в алфавитном порядке, чтобы такой случай не оставался таким, как автомобиль go брюки брюки автомобиль go мужчины покупают

• сначала рассортируйте строку в порядке убывания туда
  длины. Затем подберите подстроки самой длинной строки (поскольку мы
  выполняем итерацию по первому индексу и отсортировали в обратном порядке) и
  начинаем искать ее в остальных строках.

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

• В конце концов вам останутся только уникальные строки (если вы рассматриваете ["foo bar", "foo baz"] как уникальную строку.

  * 1023) *