188
правок
Изменения
Новая страница: «{{Определение |definition = '''Суффиксный автомат''' (англ. ''suffix automaton'', ''directed acyclic word graph'') {{---}} мин...»
{{Определение
|definition =
'''Суффиксный автомат''' (англ. ''suffix automaton'', ''directed acyclic word graph'') {{---}} минимальный [[Детерминированные_конечные_автоматы|ДКА]], который принимает все суффиксы строки и только их.
}}
__TOC__
==Описание==
Суффиксный автомат <tex>A</tex> для строки <tex>s</tex> представляет собой ациклический ориентированный граф, с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>.
[[Файл:Suffix_automaton_ex.png|540px|frame|center|Пример суффиксного автомата для строки <tex>abbab</tex>.]]
{{Определение
|definition =
Состояние <tex>q</tex> '''принимает строку''' <tex>s</tex>, если существует путь из начального состояния в <tex>q</tex>, такой, что если последовательно выписать буквы на рёбрах на пути, получим строку <tex>s</tex>.
}}
{{Определение
|definition =
Автомат '''принимает строку''' <tex>s</tex>, если её принимает хотя бы одно из финальных состояний.
}}
Так как автомат детерминированный, то каждому пути соответствует строка.
Если две строки <tex>a</tex> и <tex>b</tex> принимаются одним состоянием <tex>q</tex> произвольного автомата, то для любой строки <tex>x</tex> строки <tex>ax</tex> и <tex>bx</tex> принимаются или не принимаются автоматом одновременно. Действительно, независимо от того, как мы пришли в состояние <tex>q</tex>, если мы пройдём из него по пути, соответствующему строке <tex>x</tex>, мы сможем точно сказать, в какое состояние мы попадём (в частности, будет ли оно финальным). Значит, любому состоянию <tex>q</tex> соответствует множество строк <tex>X_q</tex>, которые переводят его в одно из конечных состояний.
{{Определение
|definition =
Множество <tex>X_q</tex> называют '''правым контекстом''' состояния.
}}
Правый контекст определен не только для состояния, но и для строк, которые оно принимает {{---}} правый контекст строк совпадает с правым контекстом состояния.
{{Утверждение
|statement=Состояний в автомате не меньше, чем различных правых контекстов у подстрок строки, для которой он построен, причём в минимальном автомате достигается нижняя оценка.
|proof=Допустим, что в автомате есть два состояния <tex>q_1</tex> и <tex>q_2</tex> такие что <tex>X_{q_1} = X_{q_2}</tex>. Мы можем удалить состояние <tex>q_2</tex> и перевести переходы, ведущие в него в состояние <tex>q_1</tex>. Множество принимаемых строк от этого не изменится, следовательно, мы можем продолжать, пока количество состояний не будет равно числу попарно различных правых контекстов.
}}
Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны.
В случае суффиксного автомата правый контекст <tex>X_a</tex> строки <tex>a</tex> взаимнооднозначно соответствует множеству правых позиций вхождений строки <tex>a</tex> в строку <tex>s</tex>. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.
==Построение==
{{Определение
|definition =
Пусть длина самой короткой строки, которая принимается состоянием <tex>q</tex> равно <tex>k</tex>, тогда '''суффиксная ссылка''' <tex>link_q</tex> будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.
}}
Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>len_q</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>len_{link_q} + 1</tex>.
...
==Источники информации==
* Maxime Crochemore, Christophe Hancart, Thierry Lecroq {{---}} Algorithms on Strings
* [http://codeforces.com/blog/entry/22420| А. Кульков {{---}} Лекция по суффиксным структурам]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
|definition =
'''Суффиксный автомат''' (англ. ''suffix automaton'', ''directed acyclic word graph'') {{---}} минимальный [[Детерминированные_конечные_автоматы|ДКА]], который принимает все суффиксы строки и только их.
}}
__TOC__
==Описание==
Суффиксный автомат <tex>A</tex> для строки <tex>s</tex> представляет собой ациклический ориентированный граф, с начальной вершиной и множеством терминальных вершин, рёбра которого помечены символами <tex>s</tex>.
[[Файл:Suffix_automaton_ex.png|540px|frame|center|Пример суффиксного автомата для строки <tex>abbab</tex>.]]
{{Определение
|definition =
Состояние <tex>q</tex> '''принимает строку''' <tex>s</tex>, если существует путь из начального состояния в <tex>q</tex>, такой, что если последовательно выписать буквы на рёбрах на пути, получим строку <tex>s</tex>.
}}
{{Определение
|definition =
Автомат '''принимает строку''' <tex>s</tex>, если её принимает хотя бы одно из финальных состояний.
}}
Так как автомат детерминированный, то каждому пути соответствует строка.
Если две строки <tex>a</tex> и <tex>b</tex> принимаются одним состоянием <tex>q</tex> произвольного автомата, то для любой строки <tex>x</tex> строки <tex>ax</tex> и <tex>bx</tex> принимаются или не принимаются автоматом одновременно. Действительно, независимо от того, как мы пришли в состояние <tex>q</tex>, если мы пройдём из него по пути, соответствующему строке <tex>x</tex>, мы сможем точно сказать, в какое состояние мы попадём (в частности, будет ли оно финальным). Значит, любому состоянию <tex>q</tex> соответствует множество строк <tex>X_q</tex>, которые переводят его в одно из конечных состояний.
{{Определение
|definition =
Множество <tex>X_q</tex> называют '''правым контекстом''' состояния.
}}
Правый контекст определен не только для состояния, но и для строк, которые оно принимает {{---}} правый контекст строк совпадает с правым контекстом состояния.
{{Утверждение
|statement=Состояний в автомате не меньше, чем различных правых контекстов у подстрок строки, для которой он построен, причём в минимальном автомате достигается нижняя оценка.
|proof=Допустим, что в автомате есть два состояния <tex>q_1</tex> и <tex>q_2</tex> такие что <tex>X_{q_1} = X_{q_2}</tex>. Мы можем удалить состояние <tex>q_2</tex> и перевести переходы, ведущие в него в состояние <tex>q_1</tex>. Множество принимаемых строк от этого не изменится, следовательно, мы можем продолжать, пока количество состояний не будет равно числу попарно различных правых контекстов.
}}
Таким образом, ДКА является минимальным тогда и только тогда, когда правые контексты всех его состояний попарно различны.
В случае суффиксного автомата правый контекст <tex>X_a</tex> строки <tex>a</tex> взаимнооднозначно соответствует множеству правых позиций вхождений строки <tex>a</tex> в строку <tex>s</tex>. Таким образом, каждое состояние автомата принимает строки с одинаковым множеством правых позиций их вхождений и обратно, все строки с таким множеством позиций принимается этим состоянием.
==Построение==
{{Определение
|definition =
Пусть длина самой короткой строки, которая принимается состоянием <tex>q</tex> равно <tex>k</tex>, тогда '''суффиксная ссылка''' <tex>link_q</tex> будет вести из этого состояния в состояние, которое принимает эту же строку без первого символа.
}}
Будем обозначать длину самой длинной строки, которая принимается состоянием <tex>q</tex> как <tex>len_q</tex>. Длина самой короткой строки из <tex>q</tex> в таком случае будет равна <tex>len_{link_q} + 1</tex>.
...
==Источники информации==
* Maxime Crochemore, Christophe Hancart, Thierry Lecroq {{---}} Algorithms on Strings
* [http://codeforces.com/blog/entry/22420| А. Кульков {{---}} Лекция по суффиксным структурам]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
