E104. Suffix automaton

Источник: e-maxx.ru/algo, страница PDF 313.

Suffix automaton (или ориентированный ациклический đồ thị слов) — это мощная структура данных, которая позволяет решать множество строковых задач. НаVí dụ, с помощью суффиксного автомата можно искать все вхождения одной строки в другую, или подсчитывать количество различных подстрок данной строки — обе задачи он позволяет решать за линейное время. На интуитивном уровне, Suffix automaton можно понимать как сжатую информацию обо всех substringх данной строки. Впечатляющим фактом является то, что Suffix automaton содержит всю

информацию в настолько сжатом виде, что для строки длины

он требует лишь

памяти. Более того, он

может быть построен также за время

(если мы считаем размер алфавита

константой; в противном случае —

за время

). Исторически, впервые линейность размера суффиксного автомата была открыта в 1983 г. Blumer и др., а в 1985 — 1986 гг. были представлены первые Thuật toánы его построения за линейное время (Crochemore, Blumer и др.). Более подробно — см. список литературы в конце статьи. На английском языке Suffix automaton называется "suffix automaton" (во множественном числе — "suffix automata"), а ориентированный ациклический đồ thị слов — "directed acyclic word graph" (или просто "DAWG").

Định nghĩa суффиксного автомата

Định nghĩa. Суффиксным автоматом для данной строки

называется такой

minimum детерминированный конечный автомат, который принимает все суффиксы строки . Расшифруем это Định nghĩa.

● Suffix automaton представляет собой ориентированный ациклический đồ thị, в котором вершины

называются состояниями, а дуги đồ thịа — это переходы между этими состояниями.

● Одно из состояний

называется начальным состоянием, и оно должно быть истоком đồ thịа (т.е. из него достижимы все остальные состояния).

● Каждый переход в автомате — это дуга, помеченная некоторым символом. Все переходы, исходящие из какого-

либо состояния, обязаны иметь разные метки. (С другой стороны, из состояния может не быть переходов по

каким-либо символам.)

● Одно или несколько состояний помечены как терминальные состояния. Если мы пройдём из

начального состояния

по любому пути до какого-либо терминального состояния, и выпишем при этом метки всех пройденных дуг, то получится chuỗi, которая обязана быть одним из суффиксов строки .

● Suffix automaton содержит минимальное number вершин среди всех автоматов, удовлетворяющих описанным

выше условиям. (Минимальность числа переходов не it is required, т.к. при условии минимальности числа состояний в автомате не может быть "лишних" путей — иначе это нарушило бы предыдущее свойство.)

Простейшие свойства суффиксного автомата

Простейшим, и вместе с тем важнейшим свойством суффиксного автомата является то, что он содержит в

себе информацию обо всех substringх строки

. А именно, любой путь из начального состояния

, если

мы выпишем метки дуг вдоль этого пути, образует обязательно подстроку строки

. И наоборот, любой

подстроке строки

соответствует некоторый путь, начинающийся в начальном состоянии . В целях упрощения объяснений, мы будем говорить, что подстроке соответствует тот путь из начального состояния, метки вдоль которого образуют эту подстроку. И наоборот, мы будем говорить, что любому пути соответствует та chuỗi, которую образуют метки его дуг. В каждое состояние суффиксного автомата ведёт один или несколько путей из начального состояния. Будем говорить, что состоянию соответствует набор строк, соответствующих всем этим путям.

Ví dụы построенных суффиксных автоматов

Приведём Ví dụы суффиксных автоматов, построенных для нескольких простых строк.

Начальное состояние мы будем обозначать здесь через

, а терминальные состояния — отмечать звёздочкой.

Для строки

:

Для строки

:

Для строки

:

Для строки

:

Для строки

:

Для строки

:

Для строки

:

Thuật toán построения суффиксного автомата за

линейное время

Перед тем, как перейти непосредственно к описанию Thuật toánа построения, надо ввести несколько новых понятий и доказать простые, но очень важные для понимания суффиксного автомата леммы.

Позиции окончаний

, их свойства и связь с

суффиксным автоматом

Рассмотрим любую непустую подстроку

строки

. Тогда назовём множеством окончаний

множество всех позиций в строке

, в которых оканчиваются вхождения строки

.

Мы будем называть две подстроки

и

-эквивалентными, если их множества окончаний

совпадают:

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

можно разбить

на несколько классов эквивалентности соответственно их множествам .

Оказывается, что в суффиксном автомате

-эквивалентным substringм

соответствует одно и то же состояние. Иными словами, number состояний в суффиксном автомате

равно количеству классов

-эквивалентности среди всех подстрок, плюс одно начальное состояние. Каждому состоянию суффиксного автомата соответствуют одна или несколько подстрок, имеющих одно и то же

значение

. Это утверждение мы примем как аксиому, и опишем Thuật toán построения суффиксного автомата, исходя из этого предположения — как мы затем увидим, все требуемые свойства суффиксного автомата, кроме минимальности, будут выполнены. (А минимальность следует из теоремы Nerode — см. список литературы.) Приведём также несколько простых, но важных утверждений касательно значений .

Лемма 1. Две непустые подстроки

и

(

) являются

-

эквивалентными тогда и только тогда, когда chuỗi

встречается в строке

только в виде суффикса строки

.

Chứng minh практически очевидно. В одну сторону: если

и

имеют одинаковые позиции окончаний вхождения,

то

является суффиксом

, и она присутствует в

только в виде суффикса

. В обратную сторону: если

является суффиксом

и Đầu vàoит только как этот суффикс, то их значения

равны по определению.

Лемма 2. Рассмотрим две непустые подстроки

и

(

). Тогда их

множества

либо не пересекаются, либо

целиком содержится в

, причём

это зависит от того, является

суффиксом

или нет:

Chứng minh. Предположим, что множества

и

имеют хотя бы один общий element.

Тогда это означает, что строки

и

оканчиваются в одном и том же месте, т.е.

— суффикс

. Но тогда

каждое вхождение строки

содержит на своём конце вхождение строки

, что и означает, что его

множество

целиком вкладывается в множество

.

Лемма 3. Рассмотрим некоторый класс

-эквивалентности. Отсортируем все подстроки, Đầu vàoящие в

этот класс, по невозрастанию длины. Тогда в получившейся последовательности каждая substring будет на единицу короче предыдущей, и при этом являться суффиксом предыдущей. Иными словами,

подстроки, Đầu vàoящие в один класс эквивалентности, на самом деле

являются суффиксами друг друга, и принимают всевозможные различные

длины в некотором отрезке

. Chứng minh.

Зафиксируем некоторый класс

-эквивалентности. Если он содержит только одну строку, то корректность леммы очевидна. Пусть теперь количество строк больше одной.

Согласно лемме 1, две различные

-эквивалентные строки всегда таковы, что одна является

собственным суффиксом другой. Следовательно, в одном классе

-эквивалентности не может быть

строк одинаковой длины.

Обозначим через

длиннейшую, а через

— кратчайшую строку в данном классе эквивалентности. Согласно лемме

1, chuỗi

является собственным суффиксом строки

. Рассмотрим теперь любой суффикс строки

с длиной в

отрезке

, и покажем, что он содержится в этом же классе эквивалентности. В самом

деле, этот суффикс может Đầu vàoить в

только в виде суффикса строки

(поскольку более короткий суффикс

Đầu vàoит только в виде суффикса строки

). Следовательно, согласно лемме 1, этот суффикс

-

эквивалентен строке

, что и требовалось доказать.

Суффиксные ссылки

Рассмотрим некоторое состояние автомата

. Как мы теперь знаем, состоянию

соответствует некоторый

класс строк с одинаковыми значениями

, причём если мы обозначим через

длиннейшую из этих строк, то

все остальные будут суффиксами

.

Также мы знаем, что первые несколько суффиксов строки

(если мы рассматриваем суффиксы в порядке убывания

их длины) содержатся в том же самом классе эквивалентности, а все остальные суффиксы (как минимум, пустой

суффикс) — в каких-то других классах. Обозначим через

первый такой суффикс — в него мы и проведём

суффиксную ссылку.

Иными словами, суффиксная ссылка

ведёт в такое состояние, которому

соответствует наидлиннейший суффикс строки

, находящийся в другом классе

-эквивалентности.

Здесь мы считаем, что начальному состоянию

соответствует отдельный класс эквивалентности (содержащий

только пустую строку), и полагаем

. Лемма 4. Суффиксные ссылки образуют cây, корнем которого является начальное состояние .

Chứng minh. Рассмотрим произвольное состояние

. Суффиксная ссылка

ведёт из него в

состояние, которому соответствуют строки строго меньшей длины (это следует из определения суффиксной ссылки и из леммы 3). Следовательно, двигаясь по суффиксным ссылкам, мы рано или поздно придём из состояния

в

начальное состояние

, которому соответствует пустая chuỗi.

Лемма 5. Если мы построим из всех имеющихся множеств

cây (по принципу "множество-

родитель содержит как подмножества всех своих детей"), то оно будет совпадать по структуре с câyм суффиксных ссылок. Chứng minh.

То, что из множеств

можно построить cây, следует из леммы 2 (о том, что любые два множества либо не пересекаются, либо одно содержится в другом).

Рассмотрим теперь произвольное состояние

и его суффиксную ссылку

. Из определения

суффиксной ссылки и из леммы 2 следует: что вкупе с предыдущей леммой и доказывает наше утверждение: cây суффиксных ссылок по сути своей есть

cây вкладывающихся множеств

. Приведём Ví dụ дерева суффиксных ссылок в суффиксном автомате, построенном для строки :

Промежуточный итог

Перед тем, как приступить к самому Thuật toánу, систематизируем накопленные выше знания, и введём пару вспомогательных обозначений.

● Множество подстрок строки

можно разбить на классы эквивалентности согласно их множествам окончания .

● Suffix automaton состоит из начального состояния

, а также по одному состоянию на каждый класс

-эквивалентности.

● Каждому состоянию

соответствует одна или несколько строк. Обозначим через

длиннейшую из

таких строк, через

её длину. Обозначим через

кратчайшую из таких строк, а её длину

через

. Тогда все строки, соответствующие этому состоянию, являются различными суффиксами строки

и

имеют всевозможные длины в отрезке

.

● Для каждого состояния

определена суффиксная ссылка, ведущая в такое состояние, которое

соответствует суффиксу строки

длины

. Суффиксные ссылки образуют cây

с корнем в

, причём это cây, по сути, является câyм отношений включения между множествами .

● Таким образом,

для

выражается с помощью суффиксной ссылки

как:

● Если мы стартуем из произвольного состояния

и будем идти по суффиксным ссылкам, то рано или поздно дойдём

до начального состояния

. При этом у нас получится последовательность непересекающихся

отрезков

, которые в объединении дадут один сплошной отрезок.

Thuật toán построения суффиксного автомата за линейное время

Приступим к описанию самого Thuật toánа. Thuật toán будет онлайновым, т.е. будет добавлять по одному

символу строки

, перестраивая соответствующим образом текущий автомат. Чтобы достичь линейного потребления памяти, в каждом состоянии мы будем хранить только значение

,

и список переходов из этого состояния. Метки терминальных состояний мы поддерживать не будем (мы покажем, как расставить эти метки после построения суффиксного автомата, если имеется необходимость в них).

Изначально автомат состоит из единственного состояния

, которое мы условимся считать нулевым

состоянием (остальные состояния будут получать номера

). Присвоим этому состоянию

, а

значению

присвоим для удобства

(означающее ссылку на фиктивное, несуществующее состояние). Соответственно, вся Bài toán теперь сводится к тому, чтобы реализовать обработку добавления

одного символа

в конец текущей строки. Опишем этот процесс:

● Пусть

— это состояние, соответствующее всей текущей строке до добавления символа

. (Изначально

,

а после добавления каждого символа мы будем менять значение

.)

● Создадим новое состояние

, проставив ему

. Значение

пока

считаем неопределённым.

● Сделаем такой цикл: изначально мы стоим в состоянии

; если из него нет перехода по букве

, то добавляем

этот переход по букве

в состояние

, и затем переходим по суффиксной ссылке, снова проверяя — если

нет перехода, то добавляем. Если в какой-то момент случится, что такой переход уже есть, то останавливаемся —

и обозначим через

номер состояния, на котором это произошло.

● Если ни разу не случилось, что переход по букве

уже имелся, и мы так и дошли до фиктивного состояния

(в

которое мы попали по суффиксной ссылке из начального состояния

), то мы можем просто

присвоить

и выйти.

● Допустим теперь, что мы остановились на некотором состоянии

, из которого уже был переход по букве

.

Обозначим через

то состояние, куда ведёт этот имеющийся переход.

● Теперь у нас два случая в зависимости от того,

или нет.

● Если

, то мы можем просто присвоить

и выйти.

● В противном случае, всё несколько сложнее. Необходимо произвести "клонирование" состояния

: создать

новое состояние

, скопировав в него все данные из вершины

(суффиксную ссылку, переходы), за

исключением значения

: надо присвоить

.

После клонирования мы проводим суффиксную ссылку из

в это состояние

, также

перенаправляем суффиксную ссылку из

в

. Наконец, последнее, что мы должны сделать — это пройтись от состояния

по суффиксным ссылкам, и для

каждого очередного состояния проверять: если имелся переход по букве

в состояние

, то перенаправлять его

в состояние

(а если нет, то останавливаться).

● В любом случае, чем бы ни закончилось выполнение этой процедуры, мы в конце обновляем значение

,

присваивая ему

. Если нам также нужно знать, какие вершины являются терминальными, а какие — нет, то мы можем find все терминальные вершины после построения суффиксного автомата для всей строки. Для этого рассмотрим состояние, соответствующее всей строке (оно, очевидно, у нас сохранено в переменной

), и будем идти по

его суффиксным ссылкам, пока не дойдём до начального состояния, и помечать каждое пройденное состояние как терминальное. Легко понять, что тем самым мы пометим состояния, соответствующие всем суффиксам строки

,

что нам и требовалось. В следующем разделе мы подробно рассмотрим каждый шаг Thuật toánа и покажем его корректность. Здесь же лишь отметим, что из Thuật toánа видно, что добавление одного символа приводит к добавлению одного или двух состояний в автомат. Таким образом, линейность числа состояний очевидна. Линейность числа переходов, да и вообще линейное Thời gian chạy Thuật toánа менее понятны, и они будут доказаны ниже, после доказательства корректности Thuật toánа.

Chứng minh tính đúng đắn Thuật toánа

● Назовём переход

сплошным, если

. В противном случае, т.е.

когда

, переход будем называть несплошным. Как можно увидеть из описания Thuật toánа, сплошные и несплошные переходы приводят к разным ветвям Thuật toánа. Сплошные переходы называются так потому, что, появившись впервые, они больше никогда не будут меняться. В противоположность им, несплошные переходы могут измениться при добавлении новых букв к строке (измениться может конец дуги-перехода).

● Во избежание неоднозначностей, под строкой

мы будем подразумевать строку, для которой был построен

Suffix automaton до добавления текущего символа

.

● Thuật toán начинается с того, что мы создаём новое состояние

, которому будет соответствовать вся chuỗi

. Понятно, почему мы обязаны создать новое состояние — т.к. вместе с добавлением нового символа возникает новый класс эквивалентности — это класс строк, оканчивающихся на добавляемом символе .

● После создания нового состояния Thuật toán проходится по суффиксным ссылкам, начиная с состояния,

соответствующего всей строке

, и пытается добавить переход по символу

в состояние

. Тем самым,

мы приписываем к каждому суффиксу строки

символ

. Но добавлять новые переходы мы можем только в том

случае, если они не будут конфликтовать с уже имеющимися, поэтому, как только мы встретим уже имеющийся переход

по символу

, мы сразу же обязаны остановиться.

● Самый простой случай — если мы так и дошли до фиктивного состояния

, добавив везде по новому переходу

вдоль символа

. Это означает, что символ

в строке

ранее не встречался. Мы успешно добавили все

переходы, осталось только проставить суффиксную ссылку у состояния

— она, очевидно, должна быть равна

, поскольку состоянию

в данном случае соответствуют все суффиксы строки

.

● Второй случай — когда мы наткнулись на уже имеющийся переход

. Это означает, что мы пытались добавить

в автомат строку

(где

— некоторый суффикс строки

, имеющий длину

), а эта chuỗi уже

была ранее добавлена в автомат (т.е. chuỗi

уже Đầu vàoит как substring в строку

). Поскольку

мы предполагаем, что автомат для строки

построен корректно, то новых переходов мы больше добавлять не должны. Однако возникает Complexity с тем, куда вести суффиксную ссылку из состояния

. Нам it is required

провести суффиксную ссылку в такое состояние, в котором длиннейшей строкой будет являться как раз эта самая , т.е.

для этого состояния должен быть равен

. Однако такого состояния могло и

не существовать: в таком случае нам надо произвести "расщепление" состояния.

● Итак, по одному из возможных сценариев, переход

оказался сплошным, т.е.

. В

этом случае всё просто, никакого расщепления производить не надо, и мы просто проводим суффиксную ссылку

из состояния

в состояние

.

● Другой, более сложный вариант — когда переход несплошной, т.е.

. Это означает,

что состоянию

соответствует не только нужная нам substring

длины

, но также и

подстроки большей длины. Нам ничего не остаётся, кроме как произвести "расщепление" состояния : разбить отрезок строк, соответствующих ей, на два подотрезка, так что первый будет заканчиваться как раз

длиной

.

Как производить это расщепление? Мы "клонируем" состояние

, делая его копию

с

параметром

. Мы копируем в

из

все переходы, поскольку мы не хотим

никоим образом менять пути, проходившие через

. Суффиксную ссылку из

мы ведём туда, куда

...

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct state {
            int len, link;
            map<char,int> next;
    };
    const int MAXLEN = 100000;
    state st[MAXLEN*2];
    int sz, last;
    void sa_init() {
            sz = last = 0;
            st[0].len = 0;
            st[0].link = -1;
            ++sz;
            /*
            // этот код нужен, только если автомат строится много раз для
    разных строк:
            for (int i=0; i<MAXLEN*2; ++i)
                    st[i].next.clear();
            */
    }
    void sa_extend (char c) {
            int cur = sz++;
            st[cur].len = st[last].len + 1;
            int p;
            for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
                    st[p].next[c] = cur;
            if (p == -1)
                    st[cur].link = 0;
            else {
                    int q = st[p].next[c];
                    if (st[p].len + 1 == st[q].len)
                            st[cur].link = q;
                    else {
                            int clone = sz++;
                            st[clone].len = st[p].len + 1;
                            st[clone].next = st[q].next;
                            st[clone].link = st[q].link;
                            for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                                    st[p].next[c] = clone;
                            st[q].link = st[cur].link = clone;
                    }
            }
            last = cur;
    }
    struct state {
            ...
            bool is_clon;
            int first_pos;
            List<int> inv_link;
    };
    ... после построения автомата ...
    for (int v=1; v<sz; ++v)
            st[st[v].link].inv_link.push_back (v);
    ...
    // ответ на запрос - вывод всех вхождений (возможно, с повторами)
    void output_all_occurences (int v, int P_length) {
            if (! st[v].is_clon)
                    Console.WriteLine( st[v].first_pos - P_length + 1 << endl;
            for (size_t i=0; i<st[v].inv_link.size(); ++i)
                    output_all_occurences (st[v].inv_link[i], P_length);
    }
    string lcs (string s, string t) {
            sa_init();
            for (int i=0; i<(int)s.length(); ++i)
                    sa_extend (s[i]);
            int v = 0,  l = 0,
                    best = 0,  bestpos = 0;
            for (int i=0; i<(int)t.length(); ++i) {
                    while (v && ! st[v].next.count(t[i])) {
                            v = st[v].link;
                            l = st[v].length;
                    }
                    if (st[v].next.count(t[i])) {
                            v = st[v].next[t[i]];
                            ++l;
                    }
                    if (l > best)
                            best = l,  bestpos = i;
            }
            return t.substr (bestpos-best+1, best);
    }
}

struct state {
        int len, link;
        map<char,int> next;
};
const int MAXLEN = 100000;
state st[MAXLEN*2];
int sz, last;
void sa_init() {
        sz = last = 0;
        st[0].len = 0;
        st[0].link = -1;
        ++sz;
        /*
        // этот код нужен, только если автомат строится много раз для
разных строк:
        for (int i=0; i<MAXLEN*2; ++i)
                st[i].next.clear();
        */
}
void sa_extend (char c) {
        int cur = sz++;
        st[cur].len = st[last].len + 1;
        int p;
        for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
                st[p].next[c] = cur;
        if (p == -1)
                st[cur].link = 0;
        else {
                int q = st[p].next[c];
                if (st[p].len + 1 == st[q].len)
                        st[cur].link = q;
                else {
                        int clone = sz++;
                        st[clone].len = st[p].len + 1;
                        st[clone].next = st[q].next;
                        st[clone].link = st[q].link;
                        for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                                st[p].next[c] = clone;
                        st[q].link = st[cur].link = clone;
                }
        }
        last = cur;
}
struct state {
        ...
        bool is_clon;
        int first_pos;
        vector<int> inv_link;
};
... после построения автомата ...
for (int v=1; v<sz; ++v)
        st[st[v].link].inv_link.push_back (v);
...
// ответ на запрос - вывод всех вхождений (возможно, с повторами)
void output_all_occurences (int v, int P_length) {
        if (! st[v].is_clon)
                cout << st[v].first_pos - P_length + 1 << endl;
        for (size_t i=0; i<st[v].inv_link.size(); ++i)
                output_all_occurences (st[v].inv_link[i], P_length);
}
string lcs (string s, string t) {
        sa_init();
        for (int i=0; i<(int)s.length(); ++i)
                sa_extend (s[i]);
        int v = 0,  l = 0,
                best = 0,  bestpos = 0;
        for (int i=0; i<(int)t.length(); ++i) {
                while (v && ! st[v].next.count(t[i])) {
                        v = st[v].link;
                        l = st[v].length;
                }
                if (st[v].next.count(t[i])) {
                        v = st[v].next[t[i]];
                        ++l;
                }
                if (l > best)
                        best = l,  bestpos = i;
        }
        return t.substr (bestpos-best+1, best);
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct state {
            int len, link;
            map<char,int> next;
    };
    const int MAXLEN = 100000;
    state st[MAXLEN*2];
    int sz, last;
    void sa_init() {
            sz = last = 0;
            st[0].len = 0;
            st[0].link = -1;
            ++sz;
            /*
            // этот код нужен, только если автомат строится много раз для
    разных строк:
            for (int i=0; i<MAXLEN*2; ++i)
                    st[i].next.clear();
            */
    }
    void sa_extend (char c) {
            int cur = sz++;
            st[cur].len = st[last].len + 1;
            int p;
            for (p=last; p!=-1 && !st[p].next.count(c); p=st[p].link)
                    st[p].next[c] = cur;
            if (p == -1)
                    st[cur].link = 0;
            else {
                    int q = st[p].next[c];
                    if (st[p].len + 1 == st[q].len)
                            st[cur].link = q;
                    else {
                            int clone = sz++;
                            st[clone].len = st[p].len + 1;
                            st[clone].next = st[q].next;
                            st[clone].link = st[q].link;
                            for (; p!=-1 && st[p].next[c]==q; p=st[p].link)
                                    st[p].next[c] = clone;
                            st[q].link = st[cur].link = clone;
                    }
            }
            last = cur;
    }
    struct state {
            ...
            boolean is_clon;
            int first_pos;
            ArrayList<Integer> inv_link;
    };
    ... после построения автомата ...
    for (int v=1; v<sz; ++v)
            st[st[v].link].inv_link.push_back (v);
    ...
    // ответ на запрос - вывод всех вхождений (возможно, с повторами)
    void output_all_occurences (int v, int P_length) {
            if (! st[v].is_clon)
                    System.out.println( st[v].first_pos - P_length + 1 << endl;
            for (size_t i=0; i<st[v].inv_link.size(); ++i)
                    output_all_occurences (st[v].inv_link[i], P_length);
    }
    string lcs (string s, string t) {
            sa_init();
            for (int i=0; i<(int)s.length(); ++i)
                    sa_extend (s[i]);
            int v = 0,  l = 0,
                    best = 0,  bestpos = 0;
            for (int i=0; i<(int)t.length(); ++i) {
                    while (v && ! st[v].next.count(t[i])) {
                            v = st[v].link;
                            l = st[v].length;
                    }
                    if (st[v].next.count(t[i])) {
                            v = st[v].next[t[i]];
                            ++l;
                    }
                    if (l > best)
                            best = l,  bestpos = i;
            }
            return t.substr (bestpos-best+1, best);
    }
}