#c #algorithm
#c #алгоритм
Вопрос:
Мне любопытно кое-что о текстовых алгоритмах.
Например, у нас есть двоичное слово: 1011101110001101 И как искать конкретные фиксированные подпоследовательности в этом слове?
Например, как найти самую длинную фиксированную подпоследовательность (назовем ее LFS) в word, которая имеет одинаковое количество единиц и 0?
И еще, как найти LFS, в которых больше единиц, чем 0?
Пример: word: 1001010 мы ищем LFS с одинаковым количеством единиц и нулей.
Таким образом, этот LFS был бы 100101
Но при большем количестве единиц, чем 0, мы получим: 101
Как решить это быстрее, чем O (n ^ 2)?
Крис.
Комментарии:
1. Это домашнее задание? Звучит очень похоже на это…
2. C или C ? Заголовок гласит C, теги говорят C , языки не совпадают, вопреки распространенному (ошибочному) мнению.
3. Нет, это не домашнее задание, я пытаюсь выучить любопытные вещи, потому что я собираюсь участвовать в конкурсе по ИТ в следующем году.
4. Думая об этом, на ум не приходит ни один метод, который позволил бы вам сделать это при O (n ^ 2). Первый проход создаст все подстроки, а следующий проход сравнит все подстроки длиной 1 с собранными подстроками. Следующий этап проходит всю длину 2 и так далее.
Ответ №1:
Из входных данных можно создать Trie.
Это поможет вам находить строки LFS.
Вы можете изменить алгоритм создания, чтобы подсчитывать единицы и 0, и тогда вы легко найдете эти числа в узлах подстроки.
Посмотрите также на дерево суффиксов..
Создание = O (n)
Для поиска вы, вероятно, будете делать что-то вроде BFS, которое также будет похоже на O (N)