Су́фіксний автома́т () — структура даних, що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом, який приймає всі суфікси слова і тільки їх, і що має найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами, такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова існує шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин.
Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата лінійно залежить від довжини , а також запропонували онлайн алгоритм для його побудови з лінійним часом роботи. У подальших роботах на цю тему був виявлений тісний зв'язок суфіксного автомата з суфікснимі деревами, а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до префіксного дерева для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів і приймає слова, які є суфіксами хоча б одного з цих.
За допомогою суфіксного автомата можна ефективно розв'зувати такі задачі як пошук підрядка в рядку, визначення найдовшого спільного підрядка двох і більше рядків тощо.
Застосування Суфіксний автомат рядка може використовуватися для розв'язання таких задач, як:
Підрахунок кількості різних підрядків за час в режимі онлайн, Пошук найдовшого підрядка , що входить в неї хоча б два рази, за час , Пошук найдовшого спільного підрядка рядків і за час , Підрахунок кількості входжень рядка в в якості підрядка за час , Пошук всіх входжень в за час , де — кількість входжень.
Тут варто вважати, що деякий рядок подається на вхід, коли автомат вже побудований і готовий до використання.
Суфіксні автомати також знайшли своє застосування в таких прикладних задачах, як стиснення даних, ідентифікація музики із записаних фрагментів і зіставлення геномних послідовностей.
Примітки
Література