748
правок
Изменения
→1 Основные определения. Простые комбинаторные свойства слов
'''Взяли все'''
== 1 Основные определения. Простые комбинаторные свойства слов ==
# [[Основные определения, связанные со строками]]
# [[Период и бордер, их связь]]
# [[Слово Фибоначчи]]
# [[Слово Туэ-Морса]]
# [[Декомпозиция Линдона]]<tex>^\star</tex> 0,5## заменить <tex>..</tex> на <tex>\ldots</tex>## см. также
# [[Алгоритм Ландау-Шмидта]]<tex>^\star</tex>
# [[Алгоритм Крочемора]]<tex>^\star</tex>
# [[Алгоритм Мейна-Лоренца]]<tex>^\star</tex>
# [[Алгоритм Манакера]]<tex>^\star</tex>0.5## заменить <tex>..</tex> на <tex>\ldots</tex>## <tex>d1</tex> заменить на <tex>d_1</tex>
# [[Дерево палиндромов]]<tex>^\star</tex>
# [[Наивный алгоритм поиска подстроки в строке]] 0,25
## См. также
# [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]0.5## поправить тех## решить проблемы со скобками
# [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Префикс-функция]] 01.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
## алгоритм восставноления строки - формулировка задачи не та
# [[Алгоритм Кнута-Морриса-Пратта]]
# [[Автомат Кнута-Морриса-Пратта]]
# [[Z-функция]] 0.253
## <tex>..</tex> заменить на <tex>\ldots</tex>
## Расписать более понятно, почему построение за O(n)
## алгоритм восставноления строки - формулировка задачи не та
# [[Бор]]
# [[Алгоритм Ахо-Корасик]]3## Написать более понятно
# [[Суффиксный автомат]]
# [[Алгоритм Бойера-Мура]] 0,25
=== 2 Нечёткий поиск ===
# [[Алгоритм Ландау-Вишкина (k несовпадений)]]<tex>^\star</tex> 0.25## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Ландау-Вишкина (k различий)]]<tex>^\star</tex> 0.25
## <tex>..</tex> заменить на <tex>\ldots</tex>
== 3 Суффиксное дерево ==
# [[Суффиксный бор]]0.25## <tex>..</tex> заменить на <tex>\ldots</tex>## Trie -> Tree
# [[Сжатое суффиксное дерево]]
# [[Алгоритм Укконена]]0.25## <tex>..</tex> заменить на <tex>\ldots</tex># [[Алгоритм МакКрейта]]<tex>^\star</tex> 0.25## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм Фарача]]<tex>^\star</tex>
== 4 Суффиксный массив ==
# [[Суффиксный массив]]0.25## <tex>..</tex> заменить на <tex>\ldots</tex># [[Построение суффиксного массива с помощью стандартных методов сортировки]]2## <tex>..</tex> заменить на <tex>\ldots</tex>## разобраться с псевдокодом# [[Алгоритм цифровой сортировки суффиксов циклической строки]]3## <tex>..</tex> заменить на <tex>\ldots</tex>## в картинки с примером есть ошибка## поправить тех
# [[Алгоритм Касаи и др.]]
# [[Алгоритм Карккайнена-Сандерса]]0.25## <tex>..</tex> заменить на <tex>\ldots</tex>
# [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
# [[Количество подпалиндромов в строке]]<tex>^\star</tex> 0.25## <tex>..</tex> заменить на <tex>\ldots</tex>
