Строковый алгоритм предлагает найти все общие префиксы списка строк

Question

Какой алгоритм вы бы предложили, чтобы узнать самые длинные распространенные префиксы в списке строк?

У меня могут быть такие строки, как:

Call Mike and schedule meeting.
Call Lisa
Call Adam and ask for quote.
Implement new class for iPhone project
Implement new class for Rails controller
Buy groceries

Я хочу найти следующеепрефиксы:

"Call "
"Implement new class "

Я буду использовать Objective C, поэтому готовый раствор какао будет плюсом (хотя и не обязательным).

Answer 1

Редактировать: для уточненного вопроса:

1. Сортировка строк
2. Найдите самый длинный общий префикс каждой соседней пары
3. Сортировка и дедупликация общих префиксов, затем удаление любых, являющихся строгими префиксами другого.

На самом деле, для шага (3) требуется только удалить все, что является дублированием / префиксом другого, что вы можете сделать с помощью дерева или чего-то другого вместо сортировки. Фактически может случиться так, что все это может быть сделано быстрее с соответствующим аннотированным обозначением - если вы включаете «count» для каждого узла, то вы точно ищете узлы с числом 2+, у которых нет дочерних элементов с количество 2 +.

Но сортировка встроена, и после сортировки вы можете определять префиксы, просматривая соседние элементы, так что это, вероятно, меньше усилий.

[Оригинальный ответ:

Просто одноразовая операция, найти самый длинный общий префикс среди всех строк?

Я бы, наверное, сделал это с точки зрения длины префикса. В псевдокоде и в предположении, что строки с нулевым символом в конце:

prefixlen = strlen(first_string);
foreach string in the list {
    for (i = 0; i < prefixlen; ++i) {
        if (string[i] != first_string[i]) {
            prefixlen = i;
            break;
        }
    }
    if (prefixlen == 0) break;
}

common_prefix = substring(firststring, 0, prefixlen);

* * Тысяча двадцать-одиной]

Answer 2

Вы можете вставить все свои строки в trie (он же префиксное дерево). Затем перемещайтесь по дереву от корня до тех пор, пока не найдете узел с более чем одним дочерним элементом (или просто прекратите вставку строк, когда вам потребуется добавить второй дочерний элемент к узлу).

Answer 3

Это зависит от того, что вы готовы считать префиксом.

Я полагаю, что общий ответ заключается в создании Trie (возможно, дерева суффиксов ), которое сохраняет все строки в n-арном дереве. См http://en.wikipedia.org/wiki/Trie

В зависимости от ваших критериев для «префикса» (скажем, n символов) вы можете выбрать все узлы ранга n, имеющие более одного дочернего элемента.

У вас будет список повторяющихся префиксов.

Answer 4

1. Вставить все строки в структуру данных Trie.
2. DFS от корня, чтобы найти первый узел, имеющий более 1 ребра, выходящего из него.
3. путь от корня до узла, вычисленный на шаге 2, дает самый длинный общий префикс для всего набора строк.