А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
является ли слово A подсловом слова B? Решение. Применим алгоритм КМП к слову A#B, где # | специаль- ная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A. 10.4.2. Опишите алгоритм заполнения таблицы l[1] . . . l[n]. Решение. Предположим, что первые i значений l[1] . . . l[i] уже найдены. Мы читаем очередную букву слова (т. е. x[i+1]) и должны вычислить l[i+1]. 1 i i+1 уже прочитанная часть x ⏟ ⏞ 𝑍 ⏟ ⏞ 𝑍 Другими словами, нас интересуют начала 𝑍 слова x[1] . . . x[i+1], одновременно являющиеся его концами | из них нам надо выбрать самое длинное. Откуда берутся эти начала? Каждое из них (не счи- тая пустого) получается из некоторого слова 𝑍 ′ приписыванием буквы x[i+1]. Слово 𝑍 ′ является началом и концом слова x[1] . . . x[i]. Одна- ко не любое слово, являющееся началом и концом слова x[1] . . . x[i], годится | надо, чтобы за ним следовала буква x[i+1]. Получаем такой рецепт отыскания слова 𝑍. Рассмотрим все нача- ла слова x[1] . . . x[i], являющиеся одновременно его концами. Из них выберем подходящие | те, за которыми идёт буква x[i+1]. Из подхо- дящих выберем самое длинное. Приписав в его конец x[i+1], получим искомое слово 𝑍. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и кон- цами данного слова, можно получить повторными применениями к нему функции 𝑙 из предыдущего раздела. Вот что получается: i:=1; l[1]:= 0; {таблица l[1]..l[i] заполнена правильно} while i <> n do begin len := l[i] 10.4. Алгоритм Кнута { Морриса { Пратта 185 {len - длина начала слова x[1]..x[i], которое является его концом; все более длинные начала оказались неподходящими} while (x[len+1] <> x[i+1]) and (len > 0) do begin {начало не подходит, применяем к нему функцию l} len := l[len]; end; {нашли подходящее или убедились в отсутствии} if x[len+1] = x[i+1] do begin {x[1]..x[len] - самое длинное подходящее начало} l[i+1] := len+1; end else begin {подходящих нет} l[i+1] := 0; end; i := i+1; end; 10.4.3. Докажите, что число действий в приведённом только что алгоритме не превосходит 𝐶n для некоторой константы 𝐶. Решение. Это не вполне очевидно: обработка каждой очередной бу- квы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на 1, и в этом случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что часто и сильно убывать она не может | иначе убывание не будет скомпенсировано возрастанием. Более точно, можно записать неравенство l[i+1] 6 l[i] − (число итераций на i-м шаге) + 1 или (число итераций на i-м шаге) 6 l[i] − l[i+1] + 1. Остаётся сложить эти неравенства по всем i и получить оценку сверху для общего числа итераций. 10.4.4. Будем использовать этот алгоритм, чтобы выяснить, явля- ется ли слово X длины n подсловом слова Y длины m. (Как это делать с помощью специального разделителя #, описано выше.) При этом чи- сло действий будет не более 𝐶(n + m), и используемая память тоже. Придумайте, как обойтись памятью не более 𝐶n (что может быть су- щественно меньше, если искомый образец короткий, а слово, в котором его ищут | длинное). 186 10. Сопоставление с образцом Решение. Применяем алгоритм КМП к слову A#B. При этом вычи- сление значений l[1], . . . , l[n] проводим для слова X длины n и запо- минаем эти значения. Дальше мы помним только значение l[i] для текущего i | кроме него и кроме таблицы l[1] . . . l[n], нам для вы- числений ничего не нужно. На практике слова X и Y могут не находиться подряд, поэтому про- смотр слова X и затем слова Y удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем. 10.4.5. Напишите соответствующий алгоритм (проверяющий, явля- ется ли слово X = x[1] . . . x[n] подсловом слова Y = y[1] . . . y[m]). Решение. Сначала вычисляем таблицу l[1] . . . l[n] как раньше. За- тем пишем такую программу: j:=0; len:=0; {len - длина максимального начала слова X, одновременно являющегося концом слова y[1]..y[j]} while (len <> n) and (j <> m) do begin while (x[len+1] <> y[j+1]) and (len > 0) do begin {начало не подходит, применяем к нему функцию l} len := l[len]; end; {нашли подходящее или убедились в отсутствии} if x[len+1] = y[j+1] do begin {x[1]..x[len] - самое длинное подходящее начало} len := len+1; end else begin {подходящих нет} len := 0; end; j := j+1; end; {если len=n, слово X встретилось; иначе мы дошли до конца слова Y, так и не встретив X} 10.5. Алгоритм Бойера { Мура Этот алгоритм делает то, что на первый взгляд кажется невозмож- ным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвёр- тую букву слова: если, к примеру, это буква e, то нет никакой необхо- 10.5. Алгоритм Бойера { Мура 187 димости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.) Мы приведём самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x[1] . . . x[n] | образец, который надо искать. Для каждого символа s найдём самое правое его вхождение в слово X, то есть наибольшее k, при котором x[k] = s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то нам будет удобно положить pos[s] = 0 (мы увидим дальше, почему). 10.5.1. Как заполнить массив pos? Решение. положить все pos[s] равными 0 for i:=1 to n do begin pos[x[i]]:=i; end; В процессе поиска мы будем хранить в переменной last номер бу- квы в слове, против которой стоит последняя буква образца. Вначале last = n (длина образца), затем last постепенно увеличивается. last:=n; {все предыдущие положения образца уже проверены} while last <= m do begin {слово не кончилось} if x[n] <> y[last] then begin {последние буквы разные} last := last + (n - pos[y[last]]); {n - pos[y[last]] - это минимальный сдвиг образца, при котором напротив y[last] встанет такая же буква в образце. Если такой буквы нет вообще, то сдвигаем на всю длину образца} end else begin если нынешнее положение подходит, т.е. если x[1]..x[n] = y[last-n+1]..y[last], то сообщить о совпадении; last := last+1; end; end; Знатоки рекомендуют проверку совпадения проводить справа налево, т. е. начиная с последней буквы образца (в которой совпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s], т. е. число букв в образце справа от последнего вхождения буквы s. 188 10. Сопоставление с образцом Возможны разные модификации этого алгоритма. Например, можно строку last:=last+1 заменить на last:=last+(n-u), где u | коорди- ната второго справа вхождения буквы x[n] в образец. 10.5.2. Как проще всего учесть это в программе? Решение. При построении таблицы pos написать for i:=1 to n-1 do... (далее как раньше), а в основной программе вместо last:=last+1 на- писать last:= last+n-pos[y[last]]; Приведённый нами упрощённый вариант алгоритма Бойера { Мура в некоторых случаях требует существенно больше n действий (число действий порядка mn), проигрывая алгоритму Кнута { Морриса { Прат- та. 10.5.3. Приведите пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это уста- новить. Решение. Пусть образец имеет вид baaa . . . aa, а само слово состоит только из букв a. Тогда на каждом шаге несоответствие выясняется лишь в последний момент. Настоящий (не упрощённый) алгоритм Бойера { Мура гарантиру- ет, что число действий не превосходит 𝐶(m + n) в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута { Морриса { Прат- та. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок 𝑍 (являющийся концом образца) совпал, а затем обнаружилось различие: перед 𝑍 в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нём обнаружен фрагмент, равный 𝑍, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца 𝑍 нашего образца. Как говорят знатоки, всё это (вычисление та- блицы сдвигов и её использование) можно уложить в 𝐶(m + n) действий. 10.6. Алгоритм Рабина Этот алгоритм основан на простой идее. Представим себе, что в сло- ве длины 𝑚 мы ищем образец длины 𝑛. Вырежем окошечко размера 𝑛 10.6. Алгоритм Рабина 189 и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определённую на словах длины 𝑛. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам. Что мы выигрываем при таком подходе? Казалось бы, ничего | ведь чтобы вычислить значение функции на слове в окошечке, всё рав- но нужно прочесть все буквы этого слова. Так уж лучше их сразу срав- нить с образцом. Тем не менее выигрыш возможен, и вот за счёт чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция. 10.6.1. Приведите пример удобной для вычисления функции. Решение. Заменим все буквы в слове и образце их номерами, пред- ставляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вы- честь пропавшее.) Для каждой функции существуют слова, к которым она примени- ма плохо. Зато другая функция в этом случае может работать хорошо. Возникает идея: надо запасти много функций и в начале работы алго- ритма выбирать из них случайную. (Тогда враг, желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией ему бо- роться.) 10.6.2. Приведите пример семейства удобных функций. Решение. Выберем некоторое число 𝑝 (желательно простое, см. да- лее) и некоторый вычет 𝑥 по модулю 𝑝. Каждое слово длины 𝑛 будем рассматривать как последовательность целых чисел (заменив буквы ко- дами). Эти числа будем рассматривать как коэффициенты многочле- на степени 𝑛 − 1 и вычислим значение этого многочлена по модулю 𝑝 в точке 𝑥. Это и будет одна из функций семейства (для каждой пары 𝑝 и 𝑥 получается, таким образом, своя функция). Сдвиг окошка на 1 со- ответствует вычитанию старшего члена (𝑥 𝑛−1 следует вычислить за- ранее), умножению на 𝑥 и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число 𝑝 фиксировано и к тому же простое, а 𝑋 и 𝑌 | два различных слова длины 𝑛. Тогда им соответствуют раз- личные многочлены (мы предполагаем, что коды всех букв различны | 190 10. Сопоставление с образцом это возможно, если 𝑝 больше числа букв алфавита). Совпадение значе- ний функции означает, что в точке 𝑥 эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть много- член степени 𝑛 − 1 и имеет не более 𝑛 − 1 корней. Таким образом, если 𝑛 много меньше 𝑝, то случайному 𝑥 мало шансов попасть в неудачную точку. 10.7. Более сложные образцы и автоматы Мы можем искать не конкретное слово, а подслова заданного вида. Например, можно искать слова вида a?b, где вместо ? может стоять любая буква (иными словами, нас интересует буква b на расстоянии 2 после буквы a). 10.7.1. Укажите конечный автомат, проверяющий, есть ли во вход- ном слове фрагмент вида a?b. Решение. Читая слово, следует помнить, есть ли буква a на послед- нем месте и на предпоследнем | пока не встретим искомый фрагмент. Автомат имеет состояния 00, 01, 10, 11, их смысл таков: 00 на предпоследнем и последнем местах нет a 01 на предпоследнем нет, на последнем есть 10 не предпоследнем есть, на последнем нет 11 есть и там, и там Таблица переходов автомата: Текущее Очередная Новое состояние буква состояние 00 a 01 00 не a 00 01 a 11 01 не a 10 10 a 01 10 b найдено 10 не a и не b 00 11 a 11 11 b найдено 11 не a и не b 10 Другой стандартный знак в образце | это звёздочка (*), на ме- сто которой может быть подставлено любое слово. Например, образец 10.7. Более сложные образцы и автоматы 191 ab*cd означает, что мы ищем подслово ab, за которым следует что угодно, а затем (на любом расстоянии) идёт cd. 10.7.2. Укажите конечный автомат, проверяющий, есть ли во вход- ном слове образец ab*cd (в описанном только что смысле). Решение. Текущее Очередная Новое состояние буква состояние начальное a a начальное не a начальное a b ab a a a a не a и не b начальное ab c abc ab не c ab abc d найдено abc c abc abc не c и не d ab Ещё один вид поиска | это поиск любого из слов некоторого списка. 10.7.3. Дан список слов 𝑋 1 , . . . , 𝑋 𝑘 и слово 𝑌 . Как определить, вхо- дит ли хотя бы одно из слов 𝑋 𝑖 в слово 𝑌 (как подслово)? Количество действий не должно превосходить константы, умноженной на суммар- ную длину всех слов (из списка и того, в котором происходит поиск). Решение. Очевидный способ состоит в том, чтобы каждое слово из списка проверять отдельно (с помощью одного из рассмотренных алгоритмов). Однако при этом мы не укладываемся в заданное число действий (из-за умножения 𝑘 на длину слова 𝑌 ). Посмотрим на дело с другой стороны. Каждому образцу из списка соответствует конечный автомат с некоторым множеством состояний. Эти автоматы можно объединить в один, множеством состояний ко- торого будет произведение множеств состояний всех тех автоматов. Это | очень большое множество. Однако на самом деле большинство его элементов недоступны (не могут появиться при чтении входного слова) и за счёт этого получается экономия. Примерно эту идею (но в изменённом виде) мы и будем использовать. Вспомним алгоритм Кнута { Морриса { Пратта. В нём, читая вход- ное слово, мы хранили наибольшее начало образца, являющееся кон- цом прочитанной части. Теперь нам следует хранить для каждого из 192 10. Сопоставление с образцом образцов наибольшее его начало, являющееся концом прочитанной ча- сти. Решающим оказывается такое замечание: достаточно хранить са- мое длинное из них | все остальные по нему восстанавливаются (как наибольшие начала образцов, являющиеся его концами). Склеим все образцы в дерево, объединив их совпадающие начальные участки. Например, набору образцов { aaa, aab, abab} соответствует дерево r - a r - H H H H H j a b r - * a r - b a r - b r r r Формально говоря, вершинами дерева являются все начала всех образ- цов, а сыновья вершины получаются приписыванием буквы. Читая входное слово, мы двигаемся по этому дереву: текущая вер- шина | это наибольшая (самая правая) из вершин, являющихся концом прочитанной части ( = наибольший конец прочитанной части, являю- щийся началом одного из образцов). Определим функцию 𝑙, аргументами и значениями которой являют- ся вершины дерева. Именно, 𝑙(𝑃 ) = наибольшая вершина дерева, явля- ющаяся концом 𝑃 . (Напомним, вершины дерева | это слова.) Нам по- надобится такое утверждение: 10.7.4. Пусть 𝑃 | вершина дерева. Докажите, что множество всех вершин, являющихся концами 𝑃 , равно {𝑙(𝑃 ), 𝑙(𝑙(𝑃 )), . . .} Решение. См. доказательство аналогичного утверждения для алго- ритма Кнута { Морриса { Пратта. Теперь ясно, что нужно делать, находясь в вершине 𝑃 и читая бу- кву z входного слова. Надо просматривать последовательно верши- ны 𝑃 , 𝑙(𝑃 ), 𝑙(𝑙(𝑃 )),. . . , пока не обнаружится такая, из которой выходит стрелка с буквой z. Та вершина, в которую эта стрелка ведёт, и будет нашим следующим положением. Остаётся понять, как для каждой вершины дерева вычислить указа- тель на значение функции 𝑙 в этой вершине. Это делается как раньше, при этом значения 𝑙 для более коротких слов используются при вычисле- нии очередного значения функции 𝑙. Это означает, что вершины дерева следует просматривать в порядке возрастания их длины. Нетрудно по- нять, что всё это можно уложить в требуемое число действий (хотя 10.7. Более сложные образцы и автоматы 193 константа зависит от числа букв в алфавите). Относящиеся к этому подробности см. в главе 9 Можно поинтересоваться, какие свойства слов распознаются с по- мощью конечных автоматов. Оказывается, что существует просто опи- сываемый класс образцов, задающий все такие свойства | класс регу- лярных выражений. Определение. Пусть фиксирован конечный алфавит `, не содержа- щий символов ˜, 𝜀, (, ), * и | (они будут использоваться для построения регулярных выражений и не должны перемешиваться с буквами). Ре- гулярные выражения строятся по таким правилам: (а) буква алфавита ` | регулярное выражение; (б) символы ˜, 𝜀 | регулярные выражения; (в) если 𝐴, 𝐵, 𝐶, . . . , 𝐸 | регулярные выражения, то (𝐴𝐵𝐶 . . . 𝐸) | регулярное выражение; (г) если 𝐴, 𝐵, 𝐶, . . . , 𝐸 | регулярные выражения, то (𝐴|𝐵|𝐶| . . . |𝐸) | регулярное выражение; (д) если 𝐴 | регулярное выражение, то 𝐴* | регулярное выражение. Каждое регулярное выражение задаёт множество слов в алфавите ` по таким правилам: (а) букве соответствует одноэлементное множество, состоящее из од- нобуквенного слова, состоящего из этой буквы; (б) символу 𝜀 соответствует пустое множество, а символу ˜ | одноэле- ментное множество, единственным элементом которого является пустое слово; (в) регулярному выражению (𝐴𝐵𝐶 . . . 𝐸) соответствует множество всех слов, которые можно получить, если к слову из 𝐴 приписать слово из 𝐵, затем из 𝐶,. . . , затем из 𝐸 (конкатенация множеств); (г) регулярному выражению (𝐴|𝐵|𝐶| . . . |𝐸) соответствует объеди- нение множеств, соответствующих выражениям 𝐴, 𝐵, 𝐶, . . . , 𝐸; (д) регулярному выражению 𝐴* соответствует итерация множества, соответствующего выражению 𝐴, то есть множество всех слов, которые можно так разрезать на куски, что каждый кусок при- надлежит множеству, соответствующему выражению 𝐴. (В част- ности, пустое слово всегда содержится в 𝐴*.) 194 10. Сопоставление с образцом Множества, соответствующие регулярным выражениям, называют- ся регулярными. Вот несколько примеров: Выражение Множество (a|b)* все слова из букв a и b (aa)* слова из чётного числа букв a (˜|a|b|aa|ab|ba|bb) все слова длины не более 2 из букв a, b 10.7.5. Напишите регулярное выражение, которому соответствует множество всех слов из букв a и b, в которых число букв a чётно. Решение. Выражение b* задаёт все слова без буквы a, а выражение (b* a b* a b*) | все слова ровно с двумя буквами a. Остаётся объеди- нить эти множества, а потом применить итерацию: ( (b* a b* a b*) | b* )* Другой вариант ответа: (b* a b* a)* b* 10.7.6. Напишите регулярное выражение, которое задаёт множе- ство всех слов из букв a, b, c, в которых слово bac является подсловом. Решение. ((a|b|c)* bac (a|b|c)*) 10.7.7. Напишите регулярное выражение, которое задаёт множе- ство всех слов из букв a, b, c, в которых слово bac не является под- словом. [Указание. Эта задача сложнее предыдущей; видимо, самый простой способ её решить | перейти к конечным автоматам и вернуться обрат- но (см. ниже задачу 10.7.14 ).] Теперь задачу о поиске образца в слове можно переформулировать так: проверить, принадлежит ли слово множеству, соответствующему данному регулярному выражению. 10.7.8. Какие выражения соответствуют образцам a?b и ab*cd, рас- смотренным ранее? (В образце символ * используется не в том смысле, что в регулярных выражениях!) Предполагается, что алфавит содер- жит буквы a, b, c, d, e. Решение. ((a|b|c|d|e)* a (a|b|c|d|e) b (a|b|c|d|e)*) ((a|b|c|d|e)* ab (a|b|c|d|e)* cd (a|b|c|d|e)*) 10.7. Более сложные образцы и автоматы 195 10.7.9. Докажите, что для всякого регулярного выражения можно построить конечный автомат, который распознаёт соответствующее этому выражению множество слов. Решение. Нам потребуется новое понятие | понятие источни- ка, или недетерминированного конечного автомата. Представим се- бе ориентированный граф | картинку из нескольких точек (вершин) и некоторых стрелок, соединяющих эти точки (рёбер). Пусть на неко- торых рёбрах написаны буквы (не обязательно на всех). Пусть также среди вершин выбраны две | начальная Н и конечная К. Такая кар- тинка называется источником. Будем двигаться различными способами из Н в К, читая буквы по дороге (на тех стрелках, где они есть). Каждому пути из Н в К, таким образом, соответствует некоторое слово. А источнику в целом соответ- ствует множество слов | тех слов, которые можно прочесть на путях из Н в К. Замечание. Если нарисовать состояния конечного автомата в ви- де точек, а переходы при чтении букв изобразить в виде стрелок, то станет ясно, что конечный автомат | это частный случай источника. (С дополнительными требованиями: (а) на всех стрелках, за исключе- нием ведущих в К, есть буквы; (б) для любой точки на выходящих из неё стрелках каждая буква встречается ровно один раз.) Мы будем строить конечный автомат по регулярному выражению в два приёма. Сначала мы построим источник, которому соответству- ет то же самое множество слов. Затем для произвольного источника построим автомат, который проверяет, принадлежит ли слово соот- ветствующему множеству. 10.7.10. По регулярному выражению постройте источник, задаю- щий то же множество. Решение. Индукция по построению регулярного выражения. Бу- квам соответствуют графы из одной стрелки. Объединение реализу- ется так: r - 3 Q Q Q Q Q Q s Н rН 3 rН 2 rН 1 r 3 К 3 r - К 2 r Q Q Q Q Q Q s К 1 r К 196 10. Сопоставление с образцом Нарисована картинка для объединения трёх множеств, прямоугольни- ки | это источники, им соответствующие; указаны начальные и ко- нечные вершины. На новых стрелках (их 6) букв не написано. Конкатенации соответствует картинка r - Н r Н 1 К 1 r -r Н 2 К 2 r -r Н 3 К 3 r -r К Наконец, итерации соответствует картинка s s - Н Н 1 s - J J J J ] К 1 s s К 10.7.11. Дан источник. Постройте конечный автомат, проверяю- щий, принадлежит ли входное слово соответствующему множеству (то есть можно ли прочесть это слово, идя из Н в К). Решение. Состояниями автомата будут множества вершин источ- ника. Именно, прочтя некоторое начало 𝑋 входного слова, мы будем помнить множество всех вершин источника, в которые можно пройти из начальной, прочитав на пути слово 𝑋. Тем самым задача 10.7.9 решена. Оказывается, что регулярные выражения, автоматы и источники распознают одни и те же множества. Чтобы убедиться в этом, нам осталось решить такую задачу: 10.7.12. Дан источник. Постройте регулярное выражение, задаю- щее то же множество, что и этот источник. Решение. Пусть источник имеет вершины 1, . . . , 𝑘. Будем считать, что 1 | это начало, а 𝑘 | конец. Через 𝐷 𝑖,𝑗,𝑠 обозначим множество всех слов, которые можно прочесть на пути из 𝑖 в 𝑗, если в качестве проме- жуточных пунктов разрешается использовать только вершины 1, . . . , 𝑠. Согласно определению, источнику соответствует множество 𝐷 1,𝑘,𝑘 Индукцией по 𝑠 будем доказывать регулярность всех множеств 𝐷 𝑖,𝑗,𝑠 при всех 𝑖 и 𝑗. При 𝑠 = 0 это очевидно (промежуточные вершины за- прещены, поэтому каждое из множеств состоит только из букв). 10.8. Суффиксные деревья 197 Из чего состоит множество 𝐷 𝑖,𝑗,𝑠+1 ? Отметим на пути моменты, в которых он заходит в (𝑠 + 1)-ю вершину. При этом путь разбивается на части, каждая из которых уже не заходит в неё. Поэтому легко сообразить, что 𝐷 𝑖,𝑗,𝑠+1 = 𝐷 𝑖,𝑗,𝑠 | (𝐷 𝑖,𝑠+1,𝑠 𝐷 𝑠+1,𝑠+1,𝑠 * 𝐷 𝑠+1,𝑗,𝑠 ) (вольность записи: мы используем для операций над множествами обо- значения как для регулярных выражений). Остаётся воспользоваться предположением индукции. |