Ускoрение суффикснoгo автoмaтa

#c #дерево #cpp #теория_автоматов

Имеется суффиксный автомат. Необходимо найти самую длинную пoдстpoку (oбщyю).
Автомат реализован на основе данной статьи: Суффиксный автомат.
(если с суффиксным автоматом не знакомы или статью не смотрели, дальше можно не читать)
Работает быстрее Хорспула. Но при работе с длинными строками скорости всё равно недостаточно.
Может кто-нибудь работал с подобной структурой и знает, как её можно ускорить?    

Ответы

Ответ 1

Из известных сейчас данных можно сделать вывод, что асимптотически улучшить ничего
нельзя, 500000 тысяч раз выполнять O(5*1000) с маленькой скрытой константой даст таки
4-5 секунд.
Остается попробовать уменьшить эту константу.
1) 
if (state.next[DELIM_FIRST + i] != 0)
...
for (int i = 0; i < ALPHABET; i++)
{
    if (state.next[CHAR_FIRST + i] != 0)
    {

так делать не совсем верно в плане быстродействия. map::operator[] вставляет элемент
при его отсутствии, а значит появятся пустые переходы, в которых нет необходимости.
Нужно что то такое:
if (state.next.find(DELIM_FIRST + i) != state.next.end())

а тут просто перебор:
for (std::map::const_iterator i = state.next.begin(); i!= state.next.end(); ++i)
{
    ...

Так немного ускорим обработку, убрав заранее ненужные операции.

2) Раз строк для поиска всего 5, state::result можно сделать std::bitset или свою
битовую маску на базе char/int.
3) В реализации из оригинальной статьи используется std::map для хранения переходов.
Это дает экономию памяти и быстрый перебор, но требует логарифмическое время на нахождение
перехода. Переходы эти можно сделать обычным массивом, это даст честную константу на
поиске, но придется перебирать отсутствующие переходы при переборе (в старой версии
статьи об этом было написано, не знаю почему убрали)
struct state {
    int len, link;
    int next[ALPHABET_SIZE];
};

На деле в столь маленькой std::map будет больше оверхэда (на поддержание дерева),
и она будет работать помедленнее массива. Имеет смысл поменять и посмотреть (Если сделать
так, совет #1 будет неверен).
Еще можно поменять на хэш-таблицу.
Не исключены также оптимизации исходящие из структуры входных данных.

UPD.
4) Присваивание лучше конечно убрать, вместо оператора суммы для состояния сделать
operator | (это семантически вернее отражает действие), внутри битовый OR для маски.