Сопоставление строк - одна из самых старых тем в теории алгоритмов, но по-прежнему занимает важное место в информатике. За прошедшие 20 лет мы видели технологические прорывы в таких, например, приложениях, как информационный поиск и сжатие информации. Эта книга, представляющая собой богатое собрание задач и упражнений по важнейшим вопросам алгоритмов обработки текстов и комбинаторных свойств слов, предлагает приятный и прямой путь к их изучению и практическому освоению.
Задачи взяты из многочисленных публикаций - как уже ставших классическими, так и сравнительно новых. Начав с основ, авторы рассматривают все более сложные задачи по комбинаторным свойствам слов (включая слова Фибоначчи и Туэ-Морса), поиску строк в тексте (включая алгоритмы Кнута-Морриса-Пратта и Бойера-Мура), эффективным структурам данных для представления текстов (включая суффиксные деревья и суффиксные массивы) и сжатия текста (включая методы Хаффмана, Лемпеля-Зива и Барроуза-Уилера).
Издание будет полезно студентам, преподавателям, школьникам для подготовки к олимпиадам по информатике, а также широкому кругу разработчиков программного обеспечения.
Переводчик: Слинкин А. А.
Sopostavlenie strok - odna iz samykh starykh tem v teorii algoritmov, no po-prezhnemu zanimaet vazhnoe mesto v informatike. Za proshedshie 20 let my videli tekhnologicheskie proryvy v takikh, naprimer, prilozhenijakh, kak informatsionnyj poisk i szhatie informatsii. Eta kniga, predstavljajuschaja soboj bogatoe sobranie zadach i uprazhnenij po vazhnejshim voprosam algoritmov obrabotki tekstov i kombinatornykh svojstv slov, predlagaet prijatnyj i prjamoj put k ikh izucheniju i prakticheskomu osvoeniju.
Zadachi vzjaty iz mnogochislennykh publikatsij - kak uzhe stavshikh klassicheskimi, tak i sravnitelno novykh. Nachav s osnov, avtory rassmatrivajut vse bolee slozhnye zadachi po kombinatornym svojstvam slov (vkljuchaja slova Fibonachchi i Tue-Morsa), poisku strok v tekste (vkljuchaja algoritmy Knuta-Morrisa-Pratta i Bojera-Mura), effektivnym strukturam dannykh dlja predstavlenija tekstov (vkljuchaja suffiksnye derevja i suffiksnye massivy) i szhatija teksta (vkljuchaja metody Khaffmana, Lempelja-Ziva i Barrouza-Uilera).
Izdanie budet polezno studentam, prepodavateljam, shkolnikam dlja podgotovki k olimpiadam po informatike, a takzhe shirokomu krugu razrabotchikov programmnogo obespechenija.
Perevodchik: Slinkin A. A.
