обработка строк

Question

строка 'привет', как вывести список всех слов и количество каждого слова.Алгоритм нормального дерева суффиксов возвращает только суффикс, означает, что среднее слово 'll' не появится.Может кто-нибудь помочь мне решить шаг за шагом?

Answer 1

Инициализация хеш-таблицы.
Используйте двойную петлю (для внутри для). Один индекс цикла будет представлять начало подстроки, а другой - конец. Убедитесь, что конечный индекс строго больше, чем начальный индекс, и что оба находятся в границах строки.
Для каждой обнаруженной подстроки проверьте, находится ли она в хэше. Если это не так - добавьте его как ключ со значением 1. Если это так - увеличьте текущее сохраненное значение.

Редактировать: согласно вашему комментарию:

for(b = 0; b < len; ++b) {
  for(e = b + 1; e <= len; ++e) {
    //process substring from index b (incl.) to index e (excl.)
  }
}

Это будет проходить строку «abcd» в следующем порядке:
a ab abc abcd b bc bcd c cd d

Answer 2

Используйте дерево префиксов вместо дерева суффиксов.Затем пробежитесь по этому дереву и на любом узле выведите строку, встреченную до сих пор, плюс количество поддеревьев, которые все еще доступны.

РЕДАКТИРОВАТЬ:

На самом деле это слишком ранои я испортил некоторую номенклатуру:

Дерево префиксов - это дерево, которое хранит общие префиксы только один раз.Дерево суффиксов хранит все суффиксы в дереве префиксов.Итак, я имел в виду здесь дерево суффиксов (которое также является особым видом дерева префиксов).

Итак, вы делаете следующее:

1. Создайте дерево суффиксов

Выполнить поиск по дереву префиксов, начиная с корня

function search( node ) {
   c = node.symbol;
   if not children.empty then
     for each child in node.children do
        sub_search = search( child )
        other_results.append( sub_search.results );
        sub_trees += sub_search.num_trees
     done
     for each result in other_results do
        append c to result
     done
     return c :: other_results
   else
     return {results = c; num_trees = 1 }
   fi
}

Если я не сделал никакой ошибки, это должно сработать.Суффиксная часть дерева суффиксов заботится об устранении всех суффиксов, а префиксная часть - об устранении всех префиксов.Поскольку оба хранятся в сокращенном виде, вы получаете строки между ними (которые, возможно, уже были сохранены вместе).Обратите внимание, что это не включает сжатие в дереве, которое обычно не требуется, если ваши строки не становятся очень длинными.