А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
10.7.13. Где ещё используется то же самое рассуждение? Ответ. В алгоритме Флойда вычисления цены кратчайшего пути, см. главу 9 (Разные алгоритмы на графах). 10.7.14. Докажите, что класс множеств, задаваемых регулярными выражениями, не изменился бы, если бы мы разрешили использовать не только объединение, но и отрицание (а следовательно, и пересечение | оно выражается через объединение и отрицание). Решение. Для автоматов переход к отрицанию очевиден. Замечание. На практике важную роль играет число состояний авто- мата. Оказывается, что тут всё не так просто, и переход от источника к автомату требует экспоненциального роста числа состояний. Подроб- ное рассмотрение связанных с этим теоретических и практических во- просов | дело особое (см. книгу Ахо, Ульмана и Сети о компиляторах). 10.8. Суффиксные деревья До сих про наши программы сначала получали образец, который на- до искать, а потом текст, в котором надо искать. В следующих задачах всё наоборот. 10.8.1. Программа получает на вход слово 𝑌 длины 𝑚 и может его обрабатывать (пока без ограничений на время и память). Затем она получает слово 𝑋 длины 𝑛 и должна сообщить, является ли оно подсло- вом слова 𝑌 . При этом число операций при обработке слова 𝑋 должно быть порядка 𝑛 (не превосходить 𝑐𝑛, где константа 𝑐 может зависеть от размера алфавита). Как написать такую программу? Решение. Пока не накладывается никаких ограничений на время и память при обработке 𝑌 , это не представляет труда. Именно, надо склеить все подслова слова 𝑌 в дерево, объединив слова с общими нача- 198 10. Сопоставление с образцом лами (как мы это делали, распознавая вхождения нескольких образцов). Например, для 𝑌 = 𝑎𝑏𝑎𝑏𝑐 получится такое дерево подслов (на ребре на- писана буква, которая добавляется при движении по этому ребру; вер- шины находятся во взаимно однозначном соответствии с подсловами слова 𝑌 ): 𝑏 𝑎 𝑐 𝑏 𝑏 𝑏 𝑎 𝑎 𝑐 𝑐 𝑐 𝑐 Пусть такое дерево построено. После этого, читая слово 𝑋 слева на- право, мы прослеживаем 𝑋 в дереве, начав с корня; слово 𝑋 будет под- словом слова 𝑌 , если при этом мы не выйдем за пределы дерева. Заметим, что аналогичная конструкция годится для любого множе- ства слов 𝑈, а не только для множества всех подслов данного слова: по- сле того как соответствующее дерево построено, мы можем про любое слово 𝑋 определить его принадлежность к 𝑈 за время, пропорциональ- ное длине 𝑋. (Надо только дополнительно хранить в вершине дерева информацию, принадлежит ли соответствующее ей слово множеству 𝑈 или лишь является началом другого слова, принадлежащего 𝑈.) 10.8.2. Решите предыдущую задачу с дополнительным ограничени- ем: объём используемой памяти пропорционален длине слова 𝑌 . Решение. Прежний способ не годится: число вершин дерева равно числу подслов слова 𝑌 , а у слова длины 𝑚 число подслов может быть порядка 𝑚 2 , а не 𝑚. Однако мы можем «сжать» наше дерево, оставив вершинами лишь точки ветвления (где больше одного сына). Тогда на рёбрах дерева надо написать уже не буквы, а куски слова 𝑌 . Вот что получится при сжатии нашего примера: 𝑏 𝑎𝑏 𝑐 𝑐 𝑎𝑏𝑐 𝑐 𝑎𝑏𝑐 Будем считать (здесь и далее), что последняя буква слова 𝑌 больше в нём не встречается. (Этого всегда можно достичь, дописав допол- нительный фиктивный символ.) Тогда листья сжатого дерева соответ- ствуют концам слова 𝑌 , а внутренние вершины (точки ветвления) | 10.8. Суффиксные деревья 199 таким подсловам 𝑠 слова 𝑌 , которые встречаются в 𝑌 несколько раз, и притом с разными буквами после 𝑠. У каждой внутренней вершины (не листа) сжатого дерева есть не менее двух сыновей. В деревьях с такими свойствами число внутренних вершин не превосходит числа листьев. (В самом деле, при движении сле- ва направо в каждой точке ветвления добавляется новый путь к листу.) Поскольку листьев 𝑚, всего вершин не более 2𝑚, и мы уложимся в ли- нейную по 𝑚 память, если будем экономно хранить пометки на рёбрах. Каждая такая пометка является подсловом слова 𝑌 , и потому доста- точно указывать координату её начала и конца в 𝑌 . Это не помешает впоследствии прослеживать произвольное слово 𝑋 в этом дереве буква за буквой, просто в некоторые моменты мы будем находиться внутри рёбер (и должны помнить, внутри какого ребра и в какой позиции мы находимся). При появлении новой буквы слова 𝑋 её нужно сравнить с соответствующей буквой пометки этого ребра (что можно сделать за 𝑂(1) действий, так как координату этой буквы мы знаем.) Построенное нами сжатое дерево называют сжатым суффиксным деревом слова 𝑌 (концы слова называют «суффиксами»). 10.8.3. Покажите, что построение сжатого суффиксного дерева можно выполнить за время 𝑂(𝑚 2 ) с использованием 𝑂(𝑚) памяти. Решение. Будем добавлять в суффиксное дерево суффиксы по очере- ди. Добавление очередного суффикса делается так же, как и проверка принадлежности: мы читаем его буква за буквой и прокладываем путь в дереве. В некоторый момент добавляемый суффикс выйдет за пре- делы дерева (напомним, что мы считаем, что последний символ слова уникален). Если это произойдёт посередине ребра, то ребро придётся в этом месте разрезать. Ребро превратится в два, его пометка разрежется на две, появится новая вершина (точка ветвления) и её новый сын-лист. Если точка ветвления совпадёт с уже имевшейся в дереве, то у неё появится новый сын-лист. В любом случае после обнаружения места ветвления требуется 𝑂(1) операций для перестройки дерева (в частно- сти, разрезание пометки на две выполняется легко, так как пометки хранятся в виде координат начала и конца в слове 𝑌 ). Гораздо более сложной задачей является построение сжатого суф- фиксного дерева за линейное время (вместо квадратичного, как в пре- дыдущей задаче). Чтобы изложить алгоритм Маккрейта, который ре- шает эту задачу, нам понадобятся некоторые приготовления. Для начала опишем более подробно структуру дерева, которое мы используем, и операции с ним. 200 10. Сопоставление с образцом Мы рассматриваем деревья с корнем, на рёбрах которых написаны слова (пометки); все пометки являются подсловами некоторого заранее фиксированного слова 𝑌 . При этом выполнены такие свойства: ∙ каждая внутренняя вершина имеет хотя бы двух сыновей; ∙ пометки на рёбрах, выходящих из данной вершины, начинаются на разные буквы. Каждой вершине 𝑣 такого дерева соответствует слово, которое за- писано на пути от корня 𝑟 к вершине 𝑣. Будем обозначать это слово 𝑠(𝑣). Обозначим пометку на ребре, ведущем к 𝑣, через 𝑙(𝑣), а отца верши- ны 𝑣 | через 𝑓(𝑣). Тогда 𝑠(𝑟) = ˜ (пустое слово), а 𝑠(𝑣) = 𝑠(𝑓(𝑣)) + 𝑙(𝑣) для любой вершины 𝑣 ̸= 𝑟 (знак «+» обозначает соединение строк). Помимо вершин дерева, мы будем рассматривать позиции в нём, ко- торые могут быть расположены в вершинах, а также «внутри рёбер» (разделяя пометку этого ребра на две части). Формально говоря, по- зиция представляет собой пару (𝑣, 𝑘), где 𝑣 | вершина (отличная от корня), а 𝑘 | целое число в промежутке [0, |𝑙(𝑣)|), указывающее, на сколько букв надо вернуться от 𝑣 к корню. Здесь |𝑙(𝑣)| | длина по- метки 𝑙(𝑣); значение 𝑘 = 𝑙(𝑣) соответствовало бы предыдущей вершине и потому не допускается. К числу позиций мы добавляем также па- ру (𝑟, 0), соответствующую корню дерева. Каждой позиции 𝑝 = (𝑣, 𝑘) соответствует слово 𝑠(𝑝), которое получается удалением 𝑘 последних символов из 𝑠(𝑣). Пусть 𝑝 | произвольная позиция в дереве, а 𝑤 | слово. Пройти вдоль 𝑤, начиная с 𝑝, означает найти другую позицию 𝑞, для которой 𝑠(𝑞) = 𝑠(𝑝) + 𝑤. Если такая позиция есть, то (при описанном способе хранения пометок, когда указываются координаты их начала и конца внутри 𝑌 ) её можно найти за время, пропорциональное длине слова 𝑤. Если такой позиции нет, то в какой-то момент мы «свернём с пути»; в этот момент можно пополнить дерево, сделав отсутствующую в де- реве часть слова 𝑤 пометкой на пути к новому листу. Надо только, чтобы эта пометка была подсловом слова 𝑌 (при нашем способе хране- ния пометок); это будет гарантировано, если прослеживаемое слово 𝑤 является подсловом слова 𝑌 . Заметим, что при этом может образоваться новая вершина (если развилка оказалась внутри ребра), а может и не образоваться (если раз- вилка оказалась в вершине). Число действий при такой модификации 10.8. Суффиксные деревья 201 пропорционально длине пройденной части слова (длина непройденной не важна). Оказывается, что навигацию в дереве можно ускорить, если заранее известно, что она будет успешной. 10.8.4. Пусть для данной позиции 𝑝 и слова 𝑤 заранее известно, что в дереве есть позиция 𝑞, для которой 𝑠(𝑞) = 𝑠(𝑝) + 𝑤. Покажите, что позицию 𝑞 можно найти за время, пропорциональное числу рёбер дерева на пути от 𝑝 к 𝑞. (Это число может быть значительно меньше длины слова 𝑤, если пометки на рёбрах длинные.) Решение. В самом деле, при навигации нужно ориентироваться лишь в вершинах (выбирать исходящее ребро в зависимости от очередной буквы); в остальных местах путь однозначный и потому можно сдви- гаться сразу к концу ребра. Подведём итоги. Рассмотренный способ хранения деревьев позволя- ет (для фиксированного слова 𝑌 ) ∙ создать дерево из одного корня [𝑂(1)]; ∙ найти отца любой вершины (кроме корня) [𝑂(1)]; ∙ узнать пометку любой вершины (кроме корня), то есть пометку ведущего к ней ребра [𝑂(1)]; ∙ пройти из любой позиции 𝑝 вдоль любого слова 𝑤, если заранее известно, что мы не выйдем из дерева; результат | позиция 𝑞 в дереве, для которой 𝑠(𝑞) = 𝑠(𝑝) + 𝑤 [𝑂(число рёбер на пути)]; ∙ добавить слово 𝑤 (некоторое подслово слова 𝑌 ), начав с позиции 𝑝; если при этом в дереве нет позиции 𝑞, для которой 𝑠(𝑞) = 𝑠(𝑝) + + 𝑤, то дерево меняется и такая позиция 𝑞 создаётся (она будет листом) [𝑂(число букв в 𝑤, не вошедших в 𝑙(𝑞)]; ∙ наконец, для любого слова 𝑋 можно выяснить, найдётся ли в де- реве позиция 𝑞, для которой 𝑠(𝑞) = 𝑋 [𝑂(|𝑋|)]. В квадратных скобках указано число действий при выполнении со- ответствующих операций. Ещё мы будем хранить в вершинах дерева «суффиксные ссылки» (в каждой вершине будет не более одной ссылки на другую вершину), но сначала надо объяснить, что это такое. Начнём с полного (не сжатого) суффиксного дерева для слова 𝑌 . Каждой его вершине (кроме корня) отвечает некоторое непустое под- слово слова 𝑌 . Если мы отрежем у этого подслова последнюю букву, 202 10. Сопоставление с образцом то в дереве спустимся на один шаг к корню. Но что будет, если мы отрежем первую букву? Снова получится подслово, но оно уже будет совсем в другом месте дерева. Вот как выглядят эти переходы в нашем примере (отрезание первой буквы соответствует пунктирной стрелке): 𝑏 𝑎 𝑐 𝑏 𝑏 𝑏 𝑎 𝑎 𝑐 𝑐 𝑐 𝑐 Эти стрелки мы будем называть суффиксными ссылками, посколь- ку они соответствуют переходу от слова к его суффиксу на единицу меньшей длины. Они определены для всех вершин, кроме корня. Формально можно сказать так. Пусть 𝑤 ′ означает слово 𝑤 без пер- вой буквы (𝑤 ′ определено для любого непустого слова 𝑤). Тогда суф- фиксная ссылка ведёт из вершины 𝑝 в вершину 𝑞, если 𝑠(𝑞) = 𝑠(𝑝) ′ (на- помним, что 𝑠(𝑢) | слово, соответствующее вершине 𝑢). 10.8.5. Как связаны суффиксные ссылки двух соседних вершин (от- ца и сына)? Ответ. Они указывают на соседние вершины, и буква на соединяю- щем их ребре та же самая. 10.8.6. Докажите, что при переходе к сжатому суффиксному дереву ссылки по-прежнему идут из вершины в вершину (а не внутрь рёбер). Решение. В самом деле, по нашему предположению последняя бу- ква слова больше в нём не встречается, поэтому из листа ссылка ведёт в лист. А если вершина (отличная от корня) является точкой ветвле- ния, то соответствующее ей слово 𝑠 встречается с различными буквами после него. Другими словами, для некоторых букв 𝑎 и 𝑏 слова 𝑠𝑎 и 𝑠𝑏 являются подсловами слова 𝑌 . Отрезав от них первую букву, получим слова 𝑠 ′ 𝑎 и 𝑠 ′ 𝑏, которые также являются подсловами слова 𝑌 , поэтому и 𝑠 ′ является точкой ветвления. Вот что получится для нашего примера: 𝑏 𝑎𝑏 𝑐 𝑐 𝑎𝑏𝑐 𝑐 𝑎𝑏𝑐 10.8. Суффиксные деревья 203 Теперь мы уже готовы к изложению алгоритма Маккрейта. Сжа- тое суффиксное дерево строим постепенно, добавляя к нему суффиксы по мере уменьшения их длины. Обозначим через 𝑌 𝑖 суффикс, начинаю- щийся с 𝑖-й буквы слова 𝑌 . (Таким образом, 𝑌 1 = 𝑌 , а 𝑌 𝑚 состоит из одной буквы.) После 𝑖 шагов построения наше дерево будет хранить 𝑌 1 , . . . , 𝑌 𝑖 10.8.7. Покажите, что суффиксные ссылки в таком дереве опреде- лены корректно (ведут в другую вершину того же дерева) для всех вер- шин, кроме, возможно, последнего добавленного листа (соответствую- щего слову 𝑌 𝑖 ) и его отца. Решение. В самом деле, суффиксная ссылка из листа 𝑌 𝑗 ведёт в лист 𝑌 𝑗+1 , и потому ей есть куда вести. Рассмотрим теперь внутрен- нюю вершину 𝑣, не являющуюся отцом последнего листа. Пусть в ней разветвляются два пути в листья 𝑌 𝑗 и 𝑌 𝑘 . Без ограничения общности можно считать, что 𝑗, 𝑘 < 𝑖 (если один из путей ведёт в 𝑌 𝑖 , то его можно заменить другим, ведь вершина 𝑣 по предположению не последняя раз- вилка на этом пути). Отрезав от этих путей первый символ, получим пути в листья 𝑌 𝑗+1 и 𝑌 𝑘+1 ; эти пути присутствуют в дереве (посколь- ку 𝑗 + 1 и 𝑘 + 1 не превосходят 𝑖), а точка их развилки будет концом суффиксной ссылки вершины 𝑣. Суффиксные ссылки для листьев нам не понадобятся, и вычислять мы их не будем, а для всех остальных вершин дерева мы их будем вы- числять и хранить. Более точно, после 𝑖 шагов алгоритма ∙ в дереве хранятся слова 𝑌 1 , . . . 𝑌 𝑖 (и все их начала); ∙ адрес листа, соответствующего последнему добавленному суф- фиксу (𝑌 𝑖 ) хранится в переменной last; ∙ для всех внутренних вершин дерева, кроме, быть может, отца вер- шины last, хранится правильная суффиксная ссылка. Надо понять, как поддерживать это при добавлении очередного суффикса. Можно, не мудрствуя лукаво, добавлять 𝑌 𝑖+1 буква за бу- квой, начиная с корня дерева. (Именно так мы раньше и делали, и это требовало квадратичного времени.) Какие тут возможны оптимизации? Первая связана с тем, что мы можем двигаться по дереву быстрее, если знаем, что заведомо из него не выйдем. Вторая связана с использованием суффиксных ссылок. Оба варианта предполагают, что отец 𝑢 листа last не совпадает с корнем. (Если совпадает, нам придётся добавлять 𝑌 𝑖+1 от корня.) 204 10. Сопоставление с образцом Пусть tail | пометка листа last, а head = 𝑠(𝑢); другими словами, слово head соответствует вершине 𝑢. Тогда 𝑌 𝑖 = head + tail. Отрезая первую букву, получаем 𝑌 𝑖+1 = head ′ + tail. Заметим, что head ′ заведомо не выходит за пределы дерева. В са- мом деле, 𝑢 было точкой ветвления, поэтому помимо листа 𝑌 𝑖 через точку 𝑢 проходил и лист 𝑌 𝑗 с 𝑗 < 𝑖. Тогда 𝑌 𝑗 начинается на head, а 𝑌 𝑗+1 начинается на head ′ и уже есть в дереве. Поэтому мы можем сначала проследить head ′ (найти позицию 𝑣, для которой 𝑠(𝑣) = head ′ ), а потом уже добавить tail, начиная с 𝑣. head tail last [𝑌 i ] [𝑌 j ] 𝑢 Первый способ оптимизации: head ′ заведомо есть в дереве. Эта оптимизация никак не использует суффиксных ссылок. Второй способ оптимизации их использует и позволяет (в том случае, когда применим) обойтись без прослеживания 𝑌 𝑖+1 от корня (как ускорен- ного, так и обычного). Пусть на пути к листу last, представляющему суффикс 𝑌 𝑖 , имеется вершина 𝑣, у которой суффиксная ссылка указы- вает на вершину 𝑤, так что 𝑠(𝑤) = 𝑠(𝑣) ′ . Пусть 𝑝 | слово на пути от 𝑣 к last. Тогда 𝑌 𝑖 = 𝑠(𝑣) + 𝑝, 𝑌 𝑖+1 = 𝑌 ′ 𝑖 = 𝑠(𝑣) ′ + 𝑝 = 𝑠(𝑤) + 𝑝, и для добавления 𝑌 𝑖+1 в дерево достаточно добавить слово 𝑝, начиная с вершины 𝑤. Второй способ оптимизации сочетается с первым: отрезок слова 𝑝 от 𝑣 до отца листа last можно проходить с уверенностью, что мы не выйдем за пределы дерева. Итак, мы можем описать действия, выполняемые при добавлении очередного суффикса 𝑌 𝑖+1 в дерево, следующим образом. 10.8. Суффиксные деревья 205 𝑝 𝑝 last [𝑌 i ] [𝑌 i+1 ] 𝑣 𝑤 Второй способ оптимизации: пользуемся суффиксной ссылкой вершины на пути к last. Пусть 𝑢 | отец листа last, соответствующего последнему уже до- бавленному суффиксу 𝑌 𝑖 Случай 1: 𝑢 есть корень дерева. Тогда ни одна из оптимизаций не применима, и мы добавляем 𝑌 𝑖+1 , начиная от корня. Случай 2: 𝑢 не есть корень дерева, но отец 𝑢 есть корень дере- ва (лист last находится на высоте 2). Тогда 𝑌 𝑖 = head + tail, где head и tail | пометки вершин 𝑢 и last. Мы применяем первую оптимизацию и прослеживаем head ′ с гарантией до некоторой позиции 𝑧, а потом добавляем tail от 𝑧. Случай 3: 𝑢 не есть корень дерева и его отец 𝑣 также не есть корень дерева. Тогда для 𝑣 имеется суффиксная ссылка на некото- рую вершину 𝑤, и 𝑠(𝑤) = 𝑠(𝑣) ′ . Пусть pretail | пометка вершины 𝑢, а tail | пометка листа last, при этом 𝑌 𝑖 = 𝑠(𝑣) + pretail + tail и потому 𝑌 𝑖+1 = 𝑌 ′ 𝑖 = 𝑠(𝑤) + pretail + tail. Остаётся проследить pretail от верши- ны 𝑤 с гарантией, получив некоторую позицию 𝑧, а потом добавить tail от вершины 𝑧. Остаётся ещё понять, как поддерживать структуру суффиксных ссылок (адрес нового листа у нас получается при добавлении сам собой, так что с ним проблем нет) и оценить число действий при выполнении этих процедур последовательно для всех суффиксов. Начнём с суффиксных ссылок. По правилам они должны быть у всех внутренних вершин, кроме отца только что добавленного листа. Поэто- му нам надо заботиться об отце листа last, соответствующего 𝑌 𝑖 (этот лист перестал быть «только что добавленным»; напротив, единственная новая вершина как раз является отцом только что добавленного листа и в ней суффиксная ссылка не нужна). Это актуально в случаях 2 и 3, но в этих случаях по ходу дела была найдена нужная вершина 𝑧, куда и будет направлена суффиксная ссылка из 𝑢. Строго говоря, 𝑧 могла быть не вершиной, а позицией, но тогда после добавления она станет вершиной (отцом только что добавленного листа) | ведь в новом де- 206 10. Сопоставление с образцом реве 𝑢 уже не является отцом последнего листа, и потому суффиксная ссылка из 𝑢, как было доказано, должна вести в вершину. (Другими словами, в случаях 2 и 3, если позиция 𝑧 была внутри ребра, то в ней ребро разрезается.) Всё сказанное можно условно записать в виде такого алгоритма до- бавления суффикса 𝑌 𝑖+1 : { дерево содержит суффиксы 𝑌 1 , . . . , 𝑌 𝑖 𝑠(last) = 𝑌 𝑖 имеются корректные суффиксные ссылки для всех внутренних вершин, кроме отца листа last } 𝑢 := отец листа last; tail := пометка листа last; { 𝑌 𝑖 = 𝑠(𝑢) + tail } if 𝑢 = корень дерева then begin { 𝑌 𝑖+1 = tail ′ } добавить tail ′ , начиная с корня, полученный лист поместить в last end else begin 𝑣 := отец вершины 𝑢; pretail := пометка вершины 𝑢; { 𝑌 𝑖 = 𝑠(𝑣) + pretail + tail } if 𝑣 = корень дерева then begin { 𝑌 𝑖+1 = pretail ′ + tail } проследить pretail ′ из корня в 𝑧 end else begin 𝑤 := суффиксная ссылка вершины 𝑣; { 𝑠(𝑤) = 𝑠(𝑣) ′ , 𝑌 𝑖+1 = 𝑠(𝑤) + pretail + tail } проследить pretail из 𝑤 в 𝑧 end; { осталось добавить tail из 𝑧 и ссылку из 𝑢 в 𝑧 } if позиция 𝑧 является вершиной then begin поместить в 𝑢 ссылку на 𝑧; добавить tail, начиная с 𝑧, полученный лист поместить в last; end else begin добавить tail, начиная с 𝑧, полученный лист поместить в last; поместить в 𝑢 ссылку на отца листа last; end end; 10.8. Суффиксные деревья 207 Осталось оценить число действий, которые выполняются при после- довательном добавлении суффиксов 𝑌 1 , . . . , 𝑌 𝑚 . При добавлении каждо- го следующего суффикса выполняется ограниченное количество дей- ствий, если не считать действий при «прослеживании» и «добавлении». Нам надо установить, что общее число действий есть 𝑂(𝑚); для это- го достаточно отдельно доказать, что суммарное число действий при всех прослеживаниях есть 𝑂(𝑚) и суммарное число действий при всех добавлениях есть 𝑂(𝑚). (Заметим, что некоторые прослеживания или добавления могут быть долгими | но это компенсируется другими.) Прослеживания. Длительность прослеживания пропорциональна чи- слу 𝑘 задействованных в нём рёбер, но при этом высота последнего добавленного листа (число рёбер на пути к нему) увеличивается на 𝑘 − 𝑂(1) (по сравнению с предыдущим добавленным листом). Чтобы убедиться в этом, достаточно заметить, что в третьем случае высота вершины 𝑠(𝑤) может быть меньше высоты вершины 𝑠(𝑣) разве что на единицу, поскольку суффиксные ссылки из всех вершин на пути к 𝑣 (не считая корня, где нет суффиксной ссылки) ведут в вершины на пути к 𝑤. Поскольку высота любого листа ограничена числом 𝑚, заключаем, что общая длительность всех прослеживаний есть 𝑂(𝑚). Добавления. Рассуждаем аналогично, но следим не за высотой по- следнего листа, а за длиной его пометки. При добавлении слова tail (или tail ′ ) число действий пропорционально числу просмотренных букв, но каждая просмотренная буква (кроме, быть может, одной) уменьшает длину пометки хотя бы на единицу: в пометке остаются лишь непросмо- тренные буквы (не считая первой). Поэтому на все добавления уходит в общей сложности 𝑂(𝑚) действий. Тем самым мы доказали, что описанный алгоритм строит сжатое суффиксное дерево слова 𝑌 длины 𝑚 за 𝑂(𝑚) действий. После этого для любого слова 𝑋 длины 𝑛 можно за 𝑂(𝑛) действий выяснить, является ли 𝑋 подсловом слова 𝑌 . 10.8.8. Как модифицировать алгоритм построения суффиксного де- рева, чтобы не только узнавать, является ли данное слово 𝑋 подсловом слова 𝑌 , но и (если является) указывать место, где оно встречается (одно из таких мест, если их несколько)? Время построения должно оставаться 𝑂(|𝑌 |), время поиска подслова | 𝑂(|𝑋|). Решение. Каждая вершина сжатого суффиксного дерева соответ- ствует некоторому подслову слова 𝑌 ; в момент, когда эта вершина была добавлена в дерево, известно, в каком месте есть такое подслово, и мож- но записать в вершине, где соответствующее подслово кончается. 208 10. Сопоставление с образцом 10.8.9. Как модифицировать этот алгоритм, чтобы для каждого подслова можно было бы указывать его первое (самое левое) вхожде- ние? [Указание. При возникновении новой вершины на ребре нужно брать её первое вхождение (информация о котором есть на конце ребра), а не второе, только что обнаруженное.] 10.8.10. Как модифицировать этот алгоритм, чтобы для каждого подслова можно было бы указывать его последнее (самое правое) вхо- ждение? [Указание. Если при каждом проходе корректировать информацию вдоль пути, это будет долго; быстрее построить дерево, затем вновь его обойти и для каждой вершины вычислить момент последнего появления соответствующего подслова.] 10.8.11. Как использовать сжатое суффиксное дерево, чтобы для данного слова 𝑌 за время 𝑂(|𝑌 |) найти самое длинное подслово, которое входит в 𝑌 более одного раза? Решение. Такое подслово является внутренней вершиной сжатого суффиксного дерева, поэтому достаточно из всех его вершин взять ту, которой соответствует самое длинное слово. Для этого достаточ- но обойти все его вершины (длину можно вычислять по мере обхода, складывая длины пометок на рёбрах). На практике можно использовать также и другой способ нахожде- ния самого длинного подслова, входящего дважды, | так называемый массив суффиксов. А именно, будем рассматривать число 𝑖 как «код» конца слова, начинающего с 𝑖-й буквы. Введём на кодах порядок, со- ответствующий лексикографическому (словарному) порядку на словах: код 𝑖 предшествует коду 𝑗, если конец слова, начинающийся с 𝑖, в лекси- кографическом порядке идёт раньше конца слова, начинающегося с 𝑗. После этого отсортируем коды в соответствии с этим порядком, по- лучив некоторую перестановку массива 1, 2, 3, . . . , 𝑚 (где 𝑚 | длина исходного слова 𝑌 ). Если какое-то слово 𝑋 входит в слово 𝑌 дважды, то оно является началом двух концов слова 𝑌 . При этом эти концы можно выбрать соседними в лексикографическом порядке, поскольку все промежуточные слова тоже начинаются на 𝑋. Значит, достаточно для всех соседних концов посмотреть, сколько начальных букв у них совпадает, и взять максимум. Этот способ требует меньше памяти (нам нужен лишь один массив из целых чисел той же длины, что исходное слово), но может требо- вать большого времени: во-первых, сортировка сама по себе требует 10.8. Суффиксные деревья 209 порядка 𝑚 log 𝑚 сравнений, во-вторых, каждое сравнение может длить- ся долго, если совпадающий кусок большой. Но в случаях, когда длин- ных совпадающих кусков мало, такой алгоритм работает неплохо. 10.8.12. Примените один из таких алгоритмов к любимой книге и объясните результат. [Указание. Длинные повторяющиеся куски могут быть художествен- ным приёмом (как в известном стишке про дом, который построил Джек) или следствием забывчивости автора. Для современных авто- ров возможно также неумеренное использование функций вырезания и вставки (заливки текста в мышь и выливания из мыши, если исполь- зовать графический интерфейс) в текстовом редакторе.] 11. АНАЛИЗ ИГР 11.1. Примеры игр 11.1.1. Двое играют в такую игру: на столе лежит 20 спичек; игра- ющие по очереди могут взять от 1 до 4 спичек; кто не может сделать хода (спичек не осталось) | проигрывает. Кто выигрывает при пра- вильной игре? Решение. Второй выигрывает, если будет дополнять ход первого до 5 спичек (если первый берёт одну, второй должен взять четыре и так далее). Тогда после четырёх раундов спичек не останется и первый проиграет. 11.1.2. Кто выиграет | первый или второй | если спичек не 20, а 23? Решение. Первый: если он возьмёт три спички, то станет вторым в уже разобранной игре и потому сможет выиграть. Аналогично получается ответ и для произвольного числа спичек 𝑁: если 𝑁 кратно пяти, то выигрывает второй, а если нет, то первый. |