Главная страница

анти. Guide to Competitive


Скачать 2.39 Mb.
НазваниеGuide to Competitive
Дата20.12.2022
Размер2.39 Mb.
Формат файлаpdf
Имя файлаанти.pdf
ТипGuide
#854732
страница20 из 26
1   ...   16   17   18   19   20   21   22   23   ...   26
Глава
14
Алгоритмы работы со строками
В этой главе обсуждаются вопросы обработки строк.
В разделе 14.1 рассмотрена структура префиксного дерева для хранения множества строк. Затем обсуждаются алгоритмы динамического програм- мирования для определения наибольшей общей подпоследовательности и редакторского расстояния.
В разделе 14.2 обсуждаются методы хеширования строк, лежащие в ос- нове эффективных алгоритмов работы со строками. Идея заключается в том, чтобы сравнивать хеш-коды строк вместо символов, это позволяет сравнивать строки за постоянное время.
В разделе 14.3 мы познакомимся с Z-алгоритмом, который для каждой позиции строки находит самую длинную подстроку, одновременно явля- ющуюся префиксом строки. Z-алгоритм – альтернативный подход ко мно- гим задачам, которые можно решить также с помощью хеширования.
В разделе 14.4 обсуждается структура суффиксного массива, используе- мого для решения многих нетривиальных задач обработки строк.
14.1. Базовые методы
В этой главе предполагается, что индексирование строк начинается с 0, т. е. строка s
длины n состоит из символов s
[0],
s
[1], …,
s
[
n − 1].
Подстрокой называется последовательность соседних символов строки. s
[
a b] обозначает подстроку, которая начинается в позиции a и закан- чивается в позиции b. Префиксом называется подстрока, начинающаяся первым символом строки, а суффиксом – подстрока, заканчивающаяся по- следним символом строки.
Подпоследовательностью называется любая последовательность симво- лов строки в их исходном порядке. Любая подстрока является подпоследо- вательностью, но обратное неверно (рис. 14.1).
E
N
V
E
L
O
P
E
a substring
E
N
V
E
L
O
P
E
a subsequence
Рис. 14.1.
NVELO
–подстрока,
NEP – подпоследовательность
Подстрока
Подпоследовательность

14.1. Базовые методы

261
14.1.1. Префиксное дерево
Префиксным деревом (trie)называется корневое дерево для хранения множества строк. Каждая строка хранится в виде цепочки символов, на- чинающейся в корне. Если у двух строк имеется об- щий префикс, то у них также будет общая цепочка в дереве. Префиксное дерево на рис. 14.2 соответ- ствует множеству строк
{CANAL,
CANDY, THE, THERE}
Двойной окружностью обозначены вершины, в ко- торых некоторая строка заканчивается.
Построив префиксное дерево, мы можем легко проверить, содержит ли оно данную строку. Для этого нужно проследовать по цепочке, начинаю- щейся в корневом узле. Чтобы добавить в дерево новую строку, нужно тоже следовать по цепочке, добавляя в нужных местах новые вершины. Вре- менная сложность обеих операций равна O(n), где
n – длина строки.
Префиксное дерево можно сохранить в массиве
int trie[N][A];
где N – максимальное число вершин (суммарная длина всех строк во мно- жестве), а A – размер алфавита. Вершины дерева нумеруются числами
0, 1, 2, … таким образом, что корень имеет номер 0, а trie
[
s][c] определяет ту вершину в цепочке, в которую мы переходим из вершины s, встретив символ c.
Структуру префиксного дерева можно обобщить несколькими спосо- бами. Пусть, например, требуется вычислить количество строк с опреде- ленным префиксом. Это можно сделать эффективно, сохранив в каждой вершине дерева количество строк, чьи цепочки проходят через эту вер- шину.
14.1.2. Динамическое программирование
Методом динамического программирования можно решить много за- дач, относящихся к строкам. Ниже мы рассмотрим два примера.
Наибольшая общая подпоследовательность. Наибольшей общей под-
последовательностью двух строк называется самая длинная строка, встре- чающаяся в качестве подпоследовательности в обеих строках. Например,
OR
– наибольшая общая подпоследовательность строк
TOUR
и
OPERA
Применив динамическое программирование, мы можем определить наибольшую общую подпоследовательность двух строк x и y за время
O(nm), где n и m – длины строк. Для этого определим функцию lcs
(i, j), ко-
C
T
A
N
A
D
L
Y
H
E
R
E
Рис. 14.2. Префиксное дерево, содержащее строки
CANAL
,
CANDY
,
THE
и
THERE

262
Глава 14. Алгоритмы работы со строками торая возвращает длину наибольшей общей подпоследовательности пре- фиксов x
[0 … i] и y
[0 … j]. Тогда имеет место рекуррентное соотношение lcs
(i − 1, j – 1) + 1 x
[i
] = y
[j
]
lcs
(i, j) =

max(
lcs
(i, j − 1), lcs
(i − 1, j)) в противном случае
Идея в том, что если символы x
[i
] и y
[j
] равны, то мы их учитываем и увеличиваем длину самой длинной общей подпоследовательности на едини- цу. В противном случае удаляем последний символ из x
или y
в зависимости от того, какой выбор лучше.
На рис. 14.3 показаны значения функции lcs в нашем примере.
Редакторское расстояние. Редакторским рас-
стоянием (или расстоянием Левенштейна) между двумя строками называется наименьшее число операций редактирования, преобразующих пер- вую строку во вторую. Разрешены следующие опе- рации:
• вставка символа (например,
ABC

ABCA
);
• удаление символа (например,
ABC

AC
);
• замена символа (например,
ABC

ADC
).
Так, редакторское расстояние между строками
LOVE
и
MOVIE
равно 2, потому что мы можем сна- чала выполнить операцию
LOVE

MOVE
(замена), а затем операцию
MOVE

MOVIE
(вставка).
Вычислить редакторское расстояние между стро- ками x
и y
можно за время O(nm), где n и m – длины строк. Обозначим edit
(i, j)редакторское расстоя- ние между префиксами x
[0 … i] и y
[0 … j]. Значение этой функции можно вычислить, пользуясь рекур- рентным соотношением:
edit
(a, b) = min(
edit
(a, b − 1) + 1,
edit
(a − 1, b) + 1,
edit
(a − 1, b − 1) + cost
(a, b)),
где cost
(a, b)= 0, если x
[a
] = y
[
b], а в противном случае cost
(a, b)= 1. В этой формуле учтены три способа редактирования строки x
: вставка символа в конец x
, удаление последнего символа x
и совпадение либо замена послед- него символа x
. В последнем случае, если x
[a
] = y
[
b], последние символы можно оставить без изменения.
На рис. 14.4 показаны значения функции edit в нашем примере.
T
O
U
R
O
P
E
R
A
0 1
1 1
0 1
1 1
0 1
1 1
0 1
1 2
0 1
1 2
Рис. 14.3. Значения функции lcs для опре- деления самой длинной общей подпоследова- тельности строк
TOUR
и
OPERA
L
O
V
E
M
O
V
I
E
1 2
3 4
2 1
2 3
3 2
1 2
4 3
2 2
5 4
3 2
Рис. 14.4. Значения функции edit для определения редакторского расстояния между строками
LOVE
и
MOVIE

14.2. Хеширование строк

263
14.2. Хеширование строк
Хеширование строк позволяет эффективно отвечать на вопрос о равенстве строк, сравнивая их хеш-коды. Хеш-код – это целое число, вычисляемое по символам строки. Если две строки равны, то их хеш-коды тоже равны, благодаря чему мы можем сравнивать строки, зная хеш-коды.
14.2.1. Полиномиальное хеширование
Чаще всего реализуют полиномиальное хеширование строк, при котором хеш-код строки s
длины n вычисляется по формуле
(
s
[0]A
n
−1
+ s
[1]A
n
−2
+ … + s
[
n − 1]A
0
) mod B,
где s
[0], s
[1], …, s
[
n − 1] интерпретируются как коды символов, а A и B – за- ранее выбранные константы.
Вычислим, к примеру, хеш-код строки
ABACB
. Коды символов
A
,
B
и
C
рав- ны 65, 66, и 67. В качестве констант выберем A = 3 и B = 97. Тогда хеш-код равен
(65 · 3 4
+ 66 · 3 3
+ 65 · 3 2
+ 66 · 3 1
+ 67 · 3 0
) mod 97 = 40.
При использовании полиномиального хеширования хеш-код любой подстроки строки s
можно вычислить за время O(1)после предобработки, занимающей время O(n). Идея в том, чтобы построить массив h
– такой, что h
[
k] содержит хеш-код префикса s
[0 … k]. Элементы массива вычисля- ются рекурсивно по формуле:
h
[0] = s
[0]
h
[
k] = (
h
[
k − 1]A + s
[
k])mod B.
Дополнительно строится массив p
, для которого p
[
k] = A
k
mod B:
p
[0] = 1
p
[
k] = (
p
[
k − 1]A)mod B.
Для построения этих массивов требуется время O(n). После этого хеш- код любой подстроки s
[
a … b] можно вычислить за время O(1) по формуле
(
h
[
b] − h
[
a − 1]
p
[
b a + 1])mod B
в предположении, что a > 0. Если a = 0, то хеш-код равен просто h
[
b].
14.2.2. Применения
С помощью хеширования можно решить много задач, относящихся к строкам, потому что мы можем сравнивать произвольные подстроки строк за время O(1). Фактически хеширование зачастую позволяет сделать эффективным алгоритм полного перебора.

264
Глава 14. Алгоритмы работы со строками
Сопоставление с образцом. Фундаментальной задачей для строк является сопоставление с образцом: даны строка s и образец p, требует- ся установить, в каких позициях s встречается p. Например, образец
ABC
встречается в строке
ABCABABCA
в позициях 0 и 5 (рис. 14.5).
A
B
C
A
B
A
B
C
A
0 1
2 3
4 5
6 7
8
Рис. 14.5. Образец
ABC
встречается в строке
ABCABABCA дважды
Эту задачу можно решить за время O(n
2
)методом полного перебора: пробежаться по всем позициям s, в которых может встретиться p, и срав- нить строки посимвольно.
Но этот алгоритм можно сделать эффективным за счет хеширования, поскольку тогда каждое сравнение занимает время
O(1). Таким образом, мы получаем алгоритм с временной сложнос тью O(n).
Различные подстроки. Рассмотрим задачу о подсчете числа различных подстрок длины k заданной строки. Например, в строке
ABABAB
имеется две различные подстроки длины 3:
ABA
и
BAB
. Применив хеширование, мы мо- жем вычислить хеш-коды каждой подстроки и свести задачу к подсчету чис- ла различных целых чисел в списке, что можно сделать за время O(n log n).
Минимальная циклическая перестановка. Циклическая перестанов-
ка строки создается путем перемещения первого символа строки в конец.
Например, циклическими перестановками строки
ATLAS
являются
ATLAS
,
TLASA
,
LASAT
,
ASATL
и
SATLA
. Рассмотрим задачу о нахождении лексикогра- фически минимальной циклической перестановки строки. Например, для строки
ATLAS
таковой является циклическая перестановка
ASATL
Для эффективного решения задачи мы воспользуемся комбинацией хе- ширования строк и двоичного поиска. Ключевая идея заключается в том, что определить лексикографический порядок двух строк можно за ло- гарифмическое время. Сначала мы вычисляем длину общего префикса строк, применяя двоичный поиск. Здесь хеширование позволяет за время
O(1) проверить, совпадают ли префиксы определенной длины. Затем про- веряем следующий за общим префиксом символ, который и определяет взаимный порядок строк.
Теперь, чтобы решить задачу, мы строим строку, содержащую две рас- положенные подряд копии исходной строки (
ATLASATLAS
), и перебираем ее подстроки длины n, запоминая по ходу минимальную подстроку. Посколь- ку для одного сравнения нужно время O(log n), полная временная слож- ность алгоритма равна O(n log n).
14.2.3. Коллизии и параметры
Очевидной опасностью при сравнении хеш-кодов является коллизия – ситуация, когда строки различны, но их хеш-коды совпадают. В таком

14.2. Хеширование строк

265
случае алгоритм, основанный на хеш-кодах, заключает, что строки оди- наковы, хотя на самом деле это не так, поэтому алгоритм может давать неправильные результаты.
Избавиться от коллизий невозможно, потому что число различных строк больше числа возможных хеш-кодов. Однако вероятность коллизии мала, если константы A и B выбраны с умом. Обычно выбирают случайные константы, близкие к 10 9
, например:
A = 911382323,
B = 972663749.
При таком выборе для вычисления хеш-кодов можно использовать тип long long
, поскольку произведения AB и BB в него укладываются. Но до- статочно ли иметь примерно 10 9
различных хеш-кодов?
Рассмотрим три случая, в которых применяется хеширование.
Случай 1. Строки x и y сравниваются между собой. Вероятность коллизии равна 1/B в предположении, что все хеш-коды равновероятны.
Случай 2. Строка x сравнивается со строками y
1
, y
2
, ..., y
n
. Вероятность хотя бы одной коллизии равна
1 − (1 − 1/B)
n
.
Случай 3. Строки x
1
, x
2
, ..., x
n
сравниваются попарно. Вероятность хотя бы одной коллизии равна
1 −
B
· (B − 1) · (B − 2) ··· (Bn + 1) .
B
n
Таблица 14.1. Вероятности коллизий при разных применениях хеширования
Константа B
Случай 1
Случай 2
Случай 3
10 3
0.00 1.00 1.00 10 6
0.00 0.63 1.00 10 9
0.00 0.00 1.00 10 12 0.00 0.00 0.39 10 15 0.00 0.00 0.00 10 18 0.00 0.00 0.00
В табл. 14.1 приведены вероятности коллизий для различных значе- ний B при n = 10 6
. Как видно, в случаях 1 и 2 вероятность коллизии прене- брежимо мала, если B ≈ 10 9
. Однако в случае 3 все совсем по-другому: при
B ≈ 10 9 коллизия произойдет почти наверняка.
Ситуация в случае 3 известна под названием парадокс дней рождения: если в комнате находится n человек, то вероятность того, что какие-то два из них родились в один день, велика даже при совсем небольших n. И точ-

266
Глава 14. Алгоритмы работы со строками но так же, когда все хеш-коды сравниваются попарно, велика вероятность, что какие-то два из них одинаковы.
Вероятность коллизии можно уменьшить, если вычислять несколько хеш-кодов с разными параметрами. Крайне маловероятно, что колли- зия произойдет одновременно в нескольких хеш-кодах. Например, два хеш-кода с параметром B ≈ 10 9
эквивалентны одному хеш-коду с парамет- ром B ≈ 10 18
, при котором вероятность коллизии очень мала.
Некоторые выбирают B = 2 32
или B = 2 64
из-за удобства операций с 32- и
64-разрядными целыми числами по модулю 2 32
и 2 64
. Но это плохой выбор, поскольку можно сконструировать такие входные данные, что при любой константе вида 2
x
коллизии произойдут обязательно [27].
14.3. Z-алгоритм
Z-массив z строки s длины n для каждого k = 0, 1, ..., n − 1 содержит дли- ну максимальной (самой длинной) подстроки s
, которая начинается в позиции k и является префиксом s
. Таким образом, z
[
k] = p означает, что s
[0 ... p − 1] равно s
[
k … k + p − 1], но символы s[p] и s
[
k + p] различны (или длина строки равна k + p).
На рис. 14.6 показан Z-массив строки
ABCABCABAB
. В нем z
[3] = 5, посколь- ку подстрока
ABCAB
длины 5 является префиксом s
, а подстрока
ABCABA
дли- ны 6 таковым не является.
A
B
C
A
B
C
A
B
A
B

0 0
5 0
0 2
0 2
0 0
1 2
3 4
5 6
7 8
9
Рис. 14.6. Z-массив строки
ABCABCABAB
14.3.1. Построение Z-массива
Далее мы опишем Z-алгоритм эффективного построения Z-массива за время O(n)
1
. Алгоритм вычисляет элементы Z-массива слева направо, при этом используется уже сохраненная в массиве информация и производит- ся посимвольное сравнение строк.
Для эффективного вычисления элементов Z-массива алгоритм хранит диапазон [x, y] – такой, что s
[
x … y] – префикс s
, значение z
[x
] уже опре- делено, а значение y максимально возможное. Поскольку мы знаем, что s
[0 … y x] совпадает с s
[
x … y], то можем воспользоваться этой инфор- мацией при вычислении последующих элементов массива. Предположим, что уже вычислены элементы z
[0],
z
[1], …, z
[
k − 1] и требуется вычислить z
[
k]. Возможны три случая.
1
В работе Gusfield [15] Z-алгоритм представлен как простейший из известных методов сопоставле- ния с образцом за линейное время. При этом авторы ссылаются на оригинальную идею, изложен- ную в работе Main, Lorentz [26].

14.3. Z-алгоритм

267
Случай 1: y < k. В этом случае у нас нет информации о позиции k, поэтому мы вычисляем z
[
k], сравнивая подстроки посимвольно. Так, на рис. 14.7 диапазона [x, y] еще не существует, поэтому подстроки, начинающиеся в позициях 0 и 3, сравниваются посимвольно. Поскольку z
[3] = 5, то новым диапазоном [x, y] становится [3, 7].
A
B
C
A
B
C
A
B
A
B

0 0
?
?
?
?
?
?
?
0 1
2 3
4 5
6 7
8 9
A
B
C
A
B
C
A
B
A
B

0 0
5
?
?
?
?
?
?
0 1
2 3
4 5
6 7
8 9
x y
Рис. 14.7. Случай 1: вычисление значения z
[3]
Случай 2: y k и k + z
[
k x] ≤ y. В этом случае мы знаем, что z
[
k] = z
[
k x], потому что s
[0 … y x] и s
[
x … y] равны, и мы остаемся внутри диапазона
[x
, y]. В ситуации на рис. 14.8 мы заключаем, что z
[4] = z
[1] = 0.
A
B
C
A
B
C
A
B
A
B

0 0
5
?
?
?
?
?
?
0 1
2 3
4 5
6 7
8 9
x y
A
B
C
A
B
C
A
B
A
B

0 0
5 0
?
?
?
?
?
0 1
2 3
4 5
6 7
8 9
x y
Рис. 14.8. Случай 2: вычисление значения z
[4]
Случай 3: y k и k + z
[
k x] > y. В этом случае мы знаем, что z
[
k] ≥ y k + 1.
Однако поскольку у нас нет никакой информации после позиции y, то мы должны посимвольно сравнить подстроки, начинающиеся в позициях
y k + 1 и y + 1. Так, на рис. 14.9 мы знаем, что z
[6] ≥ 2. А поскольку s
[2] ≠ s
[8], то получается, что z
[6] = 2.
Этот алгоритм имеет временную сложность O(n), поскольку всякий раз, как при посимвольном сравнении строки два символа совпадают, значе- ние y увеличивается. Следовательно, полное время работы, необходимое для сравнения подстрок, равно всего лишь O(n).

268
Глава 14. Алгоритмы работы со строками
A
B
C
A
B
C
A
B
A
B

0 0
5 0
0
?
?
?
?
0 1
2 3
4 5
6 7
8 9
x y
A
B
C
A
B
C
A
B
A
B

0 0
5 0
0 2
?
?
?
0 1
2 3
4 5
6 7
8 9
x y
Рис. 14.9. Случай 3: вычисление значения z
[6]
14.3.2. Применения
Z-алгоритм предлагает альтернативный способ решения многих задач со строками, которые можно решить и с помощью хеширования. Но, в от- личие от хеширования, Z-алгоритм всегда дает правильные результаты без риска коллизий. Что применять на практике – хеширование или Z-ал- горитм, – зачастую дело вкуса.
Сопоставление с образцом. Снова рассмотрим задачу о сопоставлении с образцом, в которой требуется найти все вхождения образца p в строку s.
Мы уже решили ее с помощью хеширования, а теперь посмотрим, как при- менить к ней Z-алгоритм.
При обработке строк часто эксплуатируется одна и та же идея: постро- ить строку, состоящую из нескольких частей, разделенных специальными символами. В данном случае мы можем построить строку p#s, где p и s
разделены специальным символом #, не встречающимся ни в одной из строк. Тогда Z-массив строки p#s даст нам позиции вхождений p в s: это те элементы, которые содержат длину p.
На рис. 14.10
показан Z-массив для строки s =
ABCABABCA
и образца p =
ABC
В элементах 4 и 9 находится значение 3, а это значит, что p входит в s, на- чиная с позиций 0 и 5.
A
B
C
#
A
B
C
A
B
A
B
C
A

0 0
0 3
0 0
2 0
3 0
0 1
0 1
2 3
4 5
6 7
8 9
10 11 12
Рис. 14.10. Сопоставление с образцом с помощью Z-алгоритма
Нахождение границ. Границей строки s называется строка b, являю- щаяся одновременно префиксом и суффиксом s, но не совпадающая с s.
Например, границами строки
ABACABACABA
являются
A
,
ABA
и
ABACABA
. Все

14.4. Суффиксные массивы

269
границы строки можно эффективно найти с помощью Z-алгоритма, по- тому что суффикс, начинающийся в позиции k, является границей тогда и только тогда, когда k + z[k] = n,где n – длина строки. Так, на рис. 14.11 4 + z
[4] = 11, т. е.
ABACABA
– граница строки.
A
B
A
C
A
B
A
C
A
B
A

0 1
0 7
0 1
0 3
0 1
0 1
2 3
4 5
6 7
8 9
10
Рис. 14.11. Нахождение границ с помощью Z-алгоритма
14.4. Суффиксные массивы
Суффиксный массив строки описывает лекси- кографический порядок ее суффиксов. Каж- дый элемент суффиксного массива содержит начальную позицию некоторого суффикса. На рис. 14.12 показан суффиксный массив строки
ABAACBAB
Часто удобно располагать суффиксный массив вер- тикально вместе с соответствующими суффиксами
(рис. 14.13). Отметим, однако, что сам по себе суф- фиксный массив содержит только начальные пози- ции суффиксов, а не составляющие их символы.
14.4.1. Метод удвоения префикса
Простой и эффективный способ построения суф- фиксного массива строки дает метод удвоения пре-
фикса, имеющий временную сложность O(n log
2
n)
или O(n log n) в зависимости от реализации
2
. Алго- ритм состоит из раундов с номерами 0, 1, …, ⌈log
2
n⌉, на i-м раунде обрабатываются подстроки длины 2
i
В ходе раунда каждой подстроке x длины 2
i
назнача- ется целочисленная метка l(x) – такая, что l(a)= l(b), тогда и только тогда, когда a = bl(a) < l(b)тогда и только тогда, когда a < b.
На раунде 0 все подстроки состоят из одного символа, и можно исполь- зовать, например, метки
A
= 1,
B
= 2 и т. д. Если же i > 0, то на i-м раунде для построения меток подстрок длины 2
i
используются метки для подстрок длины 2
i
–1
. Чтобы назначить метку l(x)подстроке x длины 2
i
, мы разби- ваем x на две половины a и b длины 2
i
−1
с метками l(al(b). (Если вторая
2
Идея метода удвоения префикса изложена в работе Karp, Miller, Rosenberg [20]. Существуют также более эффективные алгоритмы построения суффиксного массива с временной сложностью O(n); в работе Kärkkäinen, Sanders [19] приведен пример довольно простого алгоритма такого рода.
2 6
0 3
7 1
5 4
0 1
2 3
4 5
6 7
Рис. 14.12. Суффиксный массив строки
ABAACBAB
2 6
0 3
7 1
5 4
AACBAB
AB
ABAACBAB
ACBAB
B
BAACBAB
BAB
CBAB
0 1
2 3
4 5
6 7
Рис. 14.13. Другой способ представ- ления суффиксного массива

270
Глава 14. Алгоритмы работы со строками половина начинается за пределами строки, то предполагаем, что ее метка равна 0.) Сначала мы назначаем в качестве начальной метки x пару (l(a),
l(b)). После того как всем подстрокам длины 2
i
назначены начальные мет- ки, мы сортируем эти метки и назначаем конечные метки – целые числа
1, 2, 3 и т. д. Цель назначения конечных меток состоит в том, чтобы по за- вершении последнего раунда у каждой подстроки была уникальная метка, и эти метки отражали лексикографический порядок подстрок. И наконец, на основе этих меток легко построить суффиксный массив.
На рис. 14.14 показан процесс построения меток для строки
ABAACBAB
После раунда 1 мы знаем, что l(
AB
)= 2 и l(
AA
) = 1. Поэтому на раунде 2 под- строке
ABAA
назначается начальная метка (2, 1). Поскольку существуют две меньшие начальные метки ((1, 6) и (2, 0)), то конечная метка будет равна
l(
ABAA
) = 3. Отметим, что в этом примере после раунда 2 все метки уже уникальны, потому что лексикографический порядок подстрок полностью определен первыми четырьмя символами.








1 2
1 1
3 2
1 2
initial labels final labels round 0
length 1 1, 2 2, 1 1, 1 1, 3 3, 2 2, 1 1, 2 2, 0 2
5 1
3 6
5 2
4
initial labels final labels round 1
length 2 2, 1 5, 3 1, 6 3, 5 6, 2 5, 4 2, 0 4, 0 3
6 1
4 8
7 2
5
initial labels final labels round 2
length 4 3, 8 6, 7 1, 2 4, 5 8, 0 7, 0 2, 0 5, 0 3
6 1
4 8
7 2
5
initial labels final labels round 3
length
8
Раунд 0
Длина 1
Раунд 1
Длина 2
Раунд 2
Длина 4
Раунд 3
Длина 8
Начальные метки
Начальные метки
Начальные метки
Начальные метки
Конечные метки
Конечные метки
Конечные метки
Конечные метки
Рис. 14.14. Построение меток для строки
ABAACBAB
Этот алгоритм работает за время O(n log
2
n), поскольку число раундов равно O(log n), и на каждом раунде сортируется список n пар. На самом деле возможна также реализация с временной сложностью O(n log n), поскольку для сортировки пар можно использовать алгоритм с линейным временем.
Тем не менее прямолинейная реализация со временем O(n log
2
n), для ко- торой не нужно ничего, кроме стандартной функции C++ sort
, обычно до- статочно эффективна.
14.4.2. Поиск образцов
Имея суффиксный массив, можно эффективно искать все вхождения произвольного образца в строку. Это делается за время O(k log n), где

14.4. Суффиксные массивы

271
n – длина строки, а k – длина образца. Идея заключается в том, чтобы об- рабатывать образец символ за символом и поддерживать диапазон суф- фиксного массива, который соответствует уже обработанному префиксу образца. Чтобы эффективно обновить диапазон после обработки очеред- ного символа, применяется двоичный поиск.
Найдем, например, вхождения образца
BA
в строку
ABAACBAB
(рис. 14.15).
Первоначально диапазон поиска равен [0, 7], т. е. покрывает весь суффикс- ный массив. После обработки символа B диапазон сужается до [4, 6]. Нако- нец, после обработки символа
A
остается диапазон [5, 6]. Таким образом, мы заключаем, что образец
BA
входит в строку
ABAACBAB
дважды – начиная с позиций 1 и 5.
2 6
0 3
7 1
5 4
AACBAB
AB
ABAACBAB
ACBAB
B
BAACBAB
BAB
CBAB
0 1
2 3
4 5
6 7
2 6
0 3
7 1
5 4
AACBAB
AB
ABAACBAB
ACBAB
B
BAACBAB
BAB
CBAB
0 1
2 3
4 5
6 7
2 6
0 3
7 1
5 4
AACBAB
AB
ABAACBAB
ACBAB
B
BAACBAB
BAB
CBAB
0 1
2 3
4 5
6 7
Рис. 14.15. Поиск вхождений образца
BA
в строку
ABAACBAB
с помощью суффиксного массива
По сравнению с хешированием строк и Z-алгоритмом, суффиксный мас- сив имеет то преимущество, что позволяет эффективно обрабатывать не-
сколько запросов для разных образцов, и знать эти образцы заранее при построении суффиксного массива необязательно.
14.4.3. LCP-массивы
LCP-массив строки для каждого ее суффикса дает
значение LCP: длину наибольшего общего префикса
(longest common prefix) этого суффикса и следую- щего суффикса в суффиксном массиве. На рис. 14.16 показан LCP-массив для строки
ABAACBAB
. Например, значение LCP суффикса
BAACBAB
равно 2, поскольку наибольший общий префикс
BAACBAB
и
BAB
равен
BA
Отметим, что у последнего суффикса в суффиксном массиве нет значения LCP.
Далее мы рассмотрим эффективный алгоритм
(Kasai et al. [18]) построения LCP-массива строки в предположении, что уже построен ее суффиксный
1 2
1 0
1 2
0

AACBAB
AB
ABAACBAB
ACBAB
B
BAACBAB
BAB
CBAB
0 1
2 3
4 5
6 7
Рис. 14.16. LCP-мас- сив строки
ABAACBAB

272
Глава 14. Алгоритмы работы со строками массив. Алгоритм основан на следующем наблюдении. Рассмотрим суф- фикс, для которого значение LCP равно x. Если удалить первый символ из суффикса, то значение LCP нового суффикса заведомо должно быть не меньше x − 1. Например, на рис. 14.16 значение LCP суффикса
BAACBAB
рав- но 2, поэтому значение LCP суффикса
AACBAB
должно быть не меньше 1. На самом деле оно в точности равно 1.
Воспользовавшись этим наблюдением, мы можем эффективно по- строить LCP-массив, вычисляя значения LCP в порядке убывания длины суффикса. Для каждого суффикса мы вычисляем его значение LCP, по- символьно сравнивая этот суффикс и следующий за ним в суффиксном массиве. Теперь воспользуемся тем фактом, что нам известно значение
LCP суффикса, который на один символ длиннее. Следовательно, текущее значение LCP должно быть не меньше x − 1, где x – предыдущее значение
LCP, и нам не нужно сравнивать первые x – 1 символов суффиксов. Полу- чающийся алгоритм работает за время O(n), поскольку производит всего
O(n)сравнений.
С помощью LCP-массива можно эффективно решать некоторые нетри- виальные задачи со строками. Например, чтобы вычислить количество различных подстрок строки, мы можем просто вычесть сумму всех эле- ментов LCP-массива из общего числа подстрок, т. е. ответ равен
(
1)
,
n n
c
c
+

где n – длина строки, а c – сумма всех элементов LCP-массива. Например, в строке
ABAACBAB
имеется
8 9 7
29 2

− =
различных подстрок.
14.5. Строковые автоматы
Автомат
3
– это ориентированный граф, вершины которого называются
состояниями, а ребра – переходами. Одно из состояний является началь- ным, оно помечается входящим ребром. Может существовать сколько угодно допускающих состояний, обозначаемых двойными кружками. Каж- дому переходу сопоставляется некоторый символ.
Автомат можно использовать для проверки правильности формата строки. Для этого мы стартуем в начальном состоянии, а затем обраба- тываем символы слева направо, двигаясь по переходам. Если после обра- ботки всей строки мы оказываемся в допускающем состоянии, то строка допускается, в противном случае отвергается.
3
Точнее, нас будут интересовать детерминированные конечные автоматы, или ДКА.
2

14.5. Строковые автоматы

273
В теории автоматов множество строк называется языком. Язык автомата состоит из всех допускаемых им строк. Говорят, что автомат распознает язык, если он допускает все строки, принадлежащие этому языку, и отвер- гает все прочие строки.
Например, автомат на рис. 14.17 допускает все строки, состоящие из символов
A
и
B
, в которых первый и последний символы различны, т. е. язык этого автомата состоит из строк вида
{
AB
,
BA
,
AAB
,
ABB
,
BAA
,
BBA
, ...}.
В этом автомате состояние 1 начальное, а состояния 3 и 5 допускающие.
Если на вход автомата подается строка
ABB
, то он проходит по цепочке состояний 1 → 2 → 3 → 3 и допускает строку, а если подается строка
ABA
, то он проходит по цепочке состояний 1 → 2 → 3 → 2 и отвергает строку.
1 2
3 4
5
A
B
A
A
B
B
A
B
B
A
Рис. 14.17. Автомат, допускающий все AB-строки, в которых первый и последний символы различны
Мы предполагаем, что автоматы детерминированные, т. е. не существует двух переходов из одного состояния, помеченных одним и тем же сим- волом. Это позволяет эффективно и однозначно применять автомат для обработки любой строки.
14.5.1. Регулярные языки
Язык называется регулярным, если существует распознающий его авто- мат. Например, множествов
AB
-строк, в которых первый и последний сим- волы различны, является регулярным языком, потому что его распознает автомат на рис. 14.17.
Оказывается, что язык является регулярным тогда и только тогда, ког- да существует регулярное выражение, описывающее допустимый формат принадлежащих ему строк. Регулярные выражения состоят из следующих структурных элементов:
• вертикальная черта
|
означает выбор одного из нескольких вариан- тов. Например, регулярное выражение
AB|BA|C
допускает строки
AB
,
BA
и
C
;

274
Глава 14. Алгоритмы работы со строками
• скобки
(
и
)
применяются для группировки. Например, регулярное выражение
A(A|B)C
допускает строки
AAC
и
ABC
;
• звездочка
*
означает, что предшествующую ей часть можно повто- рять произвольное число раз (в т. ч. нуль). Например, регулярное выра жение
A(BC)*
допускает строки
A
,
ABC
,
ABCBC
и т. д.
Ниже приведено регулярное выражение для автомата на рис. 14.17:
A(A|B)*B|B(A|B)*A
В этом случае имеется два варианта: либо строка начинается символом
A
и заканчивается символом
B
, либо начинается
B
и заканчивается
A
. Часть
(A|B)*
соответствует любой строке, состоящей из символов
A
и
B
Интуитивно понятно, что язык регулярный, если можно создать алго- ритм, который просматривает входную строку слева направо один раз, ис- пользует постоянный объем памяти и может определить, принадлежит ли строка языку. Например, язык
{
AB
,
AABB
,
AAABBB
,
AAAABBBB
, ...}
не является регулярным, потому что мы должны запомнить количество символов
A
, а затем проверить, что символов
B
столько же, но для произ- вольно длинных строк это невозможно сделать в памяти постоянного объ- ема.
Заметим, что в реализациях регулярных выражений в языках програм- мирования часто имеются расширения, позволяющие распознавать язы- ки, не являющиеся строго регулярными, для которых невозможно создать автомат.
14.5.2. Автоматы для сопоставления с образцом
Автомат для сопоставления с образцом можно использовать для эффек- тивного обнаружения всех вхождений образца в строку. Идея заключается в том, чтобы создать автомат, допускающий строку тогда и только тогда, когда образец является ее суффиксом. Тогда при обработке строки автомат всегда переходит в допускающее состояние, если обнаружил вхождение образца.
Если задан образец p, содержащий n символов, то автомат для сопо- ставления с ним имеет n + 1 состояний. Состояния нумеруются числами
0,1, ..., n, так что состояние 0 начальное, а единственным допускающим является состояние n. Если мы находимся в состоянии i, то уже произвели сопоставление с префиксом p[0 ... i − 1], т. е. с первыми i символами образ- ца. Далее мы переходим в состояние i + 1, если следующий входной символ совпадает с p[i], а в противном случае возвращаемся в какое-то состояние
x i.

14.5. Строковые автоматы

275
Например, на рис. 14.18 показан автомат для сопоставления с образцом
ABA
. В про- цессе обработки строки
ABABA
он переме- щается по цепочке состояний 0 → 1 → 2 →
3 → 2 → 3. В допускающее состояние 3 он попадает дважды, это значит, что образец входит в строку два раза.
Для построения автомата мы должны определить все переходы между состоя ниями. Обозначим nextState[s][c]
состояние, в которое мы перехо- дим из состояния s в результате чтения символа c. Например, на рис. 14.18 nextState[1][B]
=
2
, потому что после чтения
B
в состоянии 1 мы перехо- дим в состояние 2. Оказывается, что значения nextState можно эффек- тивно вычислить, создав сначала массив граней для образца, т. е. массив, в котором border
[i
] обозначает длину самой длинной (собственной) грани
p[0 ... i]. Например, на рис. 14.19 пока- зан массив граней образца
ABAABABAAA
В частности, border
[4] = 2, потому что
AB
– грань
ABAAB
максимальной длины.
Массив граней можно построить за время O(n)следующим образом:
border[0] = 0;
for (int i = 1; i < n; i++) {
int k = border[i-1];
while (k != 0 && p[k] != p[i]) {
k = border[k-1];
}
border[i] = (p[k] == p[i]) ? k+1 : 0;
}
Алгоритм вычисляет значения border
[i
], используя уже вычислен- ные элементы массива. Идея заключается в том, чтобы обойти грани
p[0 ... i − 1] и выбрать самую длинную грань, которую можно расширить, добавив символ p[i]. Время работы алгоритма имеет порядок O(n), потому что border
[
i + 1] ≤ border
[i
] + 1, поэтому общее число итераций цикла while равно O(n).
После построения массива граней мы можем воспользоваться формулой
s + 1 если s < n и p[s] = c
nextState
[
s][c] =

0 если s = 0

nextState
[
border
[
s − 1]][c] в противном случае для вычисления переходов. Если мы можем расширить префикс, сопостав- ленный в текущий момент, то переходим в следующее состояние. Если не
0 1
2 3
A
B
A
B
B
A
B
A
Рис. 14.18. Автомат для сопоставления с образцом
ABA
A
B
A
A
B
A
B
A
A
A
0 0
1 1
2 3
2 3
4 1
0 1
2 3
4 5
6 7
8 9
Рис. 14.19. Массив граней
ABAABABAAA

276
Глава 14. Алгоритмы работы со строками можем и находимся в состоянии 0, то в нем и остаемся. В противном случае определяем самую длинную грань текущего префикса и следуем по ранее вычисленному переходу. Пользуясь этой формулой, мы можем построить автомат для сопоставления с образцом за время O(n)в предположении, что алфавит не изменяется.
Алгоритм Кнута–Морриса–Пратта [24] – хорошо известный алгоритм сопоставления с образцом, основанный на моделировании автомата для сопоставления с образцом. Его можно рассматривать как альтернативу
Z-алгоритму (раздел 14.3).
14.5.3. Суффиксные автоматы
С
уффиксным автоматом [5] называется автомат, который допускает все суффиксы строки
4
и имеет минимальное число состояний. На рис. 14.20 показан суффиксный автомат для строки
BACA
. Он допускает суффиксы
A
,
CA
,
ACA
и
BACA
. Каждое состояние суффиксного автомата соответствует некоторому множеству строк, т. е. если мы находимся в этом состоянии, значит, произошло сопоставление с одной из строк этого множества. На- пример, на рис. 14.20 состояние 3 соответствует множеству {
C
,
AC
,
BAC
}, а состояние 5 – множеству {
A
}. Обозначим length
[x
] максимальную длину строки в состоянии x. Тогда length
[3] = 3 и length
[5] = 1. Оказывается, что все строки в некотором состоянии являются суффиксами самой длинной из них, а их длины полностью покрывают диапазоны соседних целых чи- сел. Например, в состоянии 3 все строки являются суффиксами
BAC
, а их длины образуют диапазон 1...3.
0 1
2 3
4 5
B
A
C
A
A
C
C
Рис. 14.20. Суффиксный автомат для строки
BACA
Для данной строки s длины n мы хотим создать ее суффиксный автомат за время O(n), начав с пустого автомата, имеющего только состояние 0, и добавив в него все символы по одному. Для этого мы будем хранить для каждого состояния x > 0 суффиксную ссылку link
[x
], указывающую на одно из предыдущих состояний автомата. Новый символ c добавляется в авто- мат следующим образом.
1. Обозначим x текущее последнее состояние автомата, т. е. состоя- ние, из которого не исходит ни один переход. Создадим новое
4
И только их. – Прим. ред.

14.5. Строковые автоматы

277
состоя ние y и добавим переход из x в y, помеченный c. Положим length
[y
] = length
[x
] + 1 и link
[y
] = 0.
2. Следуем по суффиксным ссылкам, исходящим из x, для каждого по- сещенного состояния добавляем новый переход в y,помеченный c, пока не найдем состояние s, в которое уже ведет переход, помечен- ный c. Если такого состояния s нет, то завершаем работу, дойдя до состояния 0. В противном случае переходим к следующему шагу.
3. Обозначим u такое состояние, для которого существует переход из s
в u, помеченный c. Если length
[
s] + 1 = length
[
u], полагаем link
[y
] = u
и завершаем работу. В противном случае переходим к следующему шагу.
4. Создаем новое состояние z, клонируя состояние u (копируем все ис- ходящие из u переходы в z и полагаем link
[z
] = link
[
u]), добавляем переход из s в z, помеченный c,и полагаем length
[z
] = length
[
s] + 1.
Затем полагаем link
[
u] = link
[y
] = z.
5. Наконец, следуем по суффиксным ссылкам, исходящим из s. До тех пор пока из текущего состояния имеется переход в состояние u, по- меченный c, заменяем u на z в этом переходе. Если мы нашли со- стояние, из которого нет перехода в u, помеченного c, или дошли до состояния 0, то завершаем работу.
На рис. 14.21 показан процесс создания суффиксного автомата для стро- ки
BACA
. После добавления последнего символа мы должны создать допол- нительное состояние 5 путем клонирования состояния 2. В этом примере все суффиксные ссылки указывают на состояние 0, и следует ожидать, что в окончательном автомате существует суффиксная ссылка из состояния 4 в состояние 5, обозначенная штриховым ребром. После создания автомата мы можем найти допускающие состояния, начав из последнего состояния и следуя по суффиксным ссылкам, пока не достигнем состояния 0. Все со- стояния на этом пути (в нашем примере – состояния 4 и 5) являются допус- кающими.
Заметим, что суффиксная ссылка говорит, в какое состояние мы должны перейти, если хотим найти более короткие строки, являющиеся суффикса- ми строк в текущем состоянии. В нашем примере состояние 4 соответству- ет множеству {
CA
,
ACA
,
BACA
}, а состояние 5 – множеству {
A
}. Таким образом, суффиксную ссылку из состояния 4 в состояние 5 можно использовать для нахождения более короткого суффикса A. На самом деле, следуя по суф- фиксным ссылкам из состояния x в состояние 0, мы найдем все суффик- сы самой длинной строки в состоянии x, и каждый суффикс принадлежит ровно одному состоянию.
После того как суффисный автомат создан, мы можем за время O(m)про- верить, встречается ли в строке любой образец длины m. Применив дина-

278
Глава 14. Алгоритмы работы со строками мическое программирование, мы сможем также найти, сколько раз встре- чается образец, вычислить количество различных подстрок и т. д. В общем случае суффиксные автоматы могут служить альтернативой суффиксным массивам, и с этой новой точки зрения можно рассмотреть многие задачи обработки строк.
0 1
B
0 1
2
B
A
A
0 1
2 3
B
A
C
C
A
0 1
2 3
4 5
B
A
C
A
A
C
C
Рис. 14.21. Построение суффиксного автомата

1   ...   16   17   18   19   20   21   22   23   ...   26


написать администратору сайта