Árbol de sufijos. Algoritmo de Ukkonen
Este artículo es un esbozo y no contiene descripciones. Para una descripción del algoritmo, consultar otras fuentes, como Algorithms on Strings, Trees, and Sequences de Dan Gusfield.
Este algoritmo construye un árbol de sufijos para un string dado de longitud en tiempo , donde es el tamaño del alfabeto (si se considera constante, el comportamiento asintótico es lineal).
La entrada del algoritmo es el string y su longitud , que se pasan como variables globales.
La función principal build_tree construye un árbol de sufijos. Se almacena como un arreglo de estructuras node, donde node[0] es la raíz del árbol.
Para simplificar el código, las aristas se almacenan en las mismas estructuras: para cada vértice su estructura node guarda la información sobre la arista entre él y su padre. En total cada node almacena la siguiente información:
(l, r)- bordes izquierdo y derecho de la subcadenas[l..r-1]que corresponde a la arista hacia este nodo,par- el nodo padre,link- el enlace de sufijo,next- la lista de aristas que salen de este nodo.
string s;
int n;
struct node {
int l, r, par, link;
map<char,int> next;
node (int l=0, int r=0, int par=-1)
: l(l), r(r), par(par), link(-1) {}
int len() { return r - l; }
int &get (char c) {
if (!next.count(c)) next[c] = -1;
return next[c];
}
};
node t[MAXN];
int sz;
struct state {
int v, pos;
state (int v, int pos) : v(v), pos(pos) {}
};
state ptr (0, 0);
state go (state st, int l, int r) {
while (l < r)
if (st.pos == t[st.v].len()) {
st = state (t[st.v].get( s[l] ), 0);
if (st.v == -1) return st;
}
else {
if (s[ t[st.v].l + st.pos ] != s[l])
return state (-1, -1);
if (r-l < t[st.v].len() - st.pos)
return state (st.v, st.pos + r-l);
l += t[st.v].len() - st.pos;
st.pos = t[st.v].len();
}
return st;
}
int split (state st) {
if (st.pos == t[st.v].len())
return st.v;
if (st.pos == 0)
return t[st.v].par;
node v = t[st.v];
int id = sz++;
t[id] = node (v.l, v.l+st.pos, v.par);
t[v.par].get( s[v.l] ) = id;
t[id].get( s[v.l+st.pos] ) = st.v;
t[st.v].par = id;
t[st.v].l += st.pos;
return id;
}
int get_link (int v) {
if (t[v].link != -1) return t[v].link;
if (t[v].par == -1) return 0;
int to = get_link (t[v].par);
return t[v].link = split (go (state(to,t[to].len()), t[v].l + (t[v].par==0), t[v].r));
}
void tree_extend (int pos) {
for(;;) {
state nptr = go (ptr, pos, pos+1);
if (nptr.v != -1) {
ptr = nptr;
return;
}
int mid = split (ptr);
int leaf = sz++;
t[leaf] = node (pos, n, mid);
t[mid].get( s[pos] ) = leaf;
ptr.v = get_link (mid);
ptr.pos = t[ptr.v].len();
if (!mid) break;
}
}
void build_tree() {
sz = 1;
for (int i=0; i<n; ++i)
tree_extend (i);
}Implementación comprimida
Esta implementación comprimida fue propuesta por freopen .
const int N=1000000,INF=1000000000;
string a;
int t[N][26],l[N],r[N],p[N],s[N],tv,tp,ts,la;
void ukkadd (int c) {
suff:;
if (r[tv]<tp) {
if (t[tv][c]==-1) { t[tv][c]=ts; l[ts]=la;
p[ts++]=tv; tv=s[tv]; tp=r[tv]+1; goto suff; }
tv=t[tv][c]; tp=l[tv];
}
if (tp==-1 || c==a[tp]-'a') tp++; else {
l[ts+1]=la; p[ts+1]=ts;
l[ts]=l[tv]; r[ts]=tp-1; p[ts]=p[tv]; t[ts][c]=ts+1; t[ts][a[tp]-'a']=tv;
l[tv]=tp; p[tv]=ts; t[p[ts]][a[l[ts]]-'a']=ts; ts+=2;
tv=s[p[ts-2]]; tp=l[ts-2];
while (tp<=r[ts-2]) { tv=t[tv][a[tp]-'a']; tp+=r[tv]-l[tv]+1;}
if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts;
tp=r[tv]-(tp-r[ts-2])+2; goto suff;
}
}
void build() {
ts=2;
tv=0;
tp=0;
fill(r,r+N,(int)a.size()-1);
s[0]=1;
l[0]=-1;
r[0]=-1;
l[1]=-1;
r[1]=-1;
memset (t, -1, sizeof t);
fill(t[1],t[1]+26,0);
for (la=0; la<(int)a.size(); ++la)
ukkadd (a[la]-'a');
}El mismo código con comentarios:
const int N=1000000, // máximo número posible de nodos en el árbol de sufijos
INF=1000000000; // constante de infinito
string a; // string de entrada para el que se construye el árbol de sufijos
int t[N][26], // arreglo de transiciones (estado, letra)
l[N], // borde izquierdo...
r[N], // ...y derecho de la subcadena de a que corresponde a la arista entrante
p[N], // padre del nodo
s[N], // enlace de sufijo
tv, // el nodo del sufijo actual (si estamos a mitad de arista, el nodo inferior de la arista)
tp, // posición en el string que corresponde a la posición en la arista (entre l[tv] y r[tv], inclusive)
ts, // el número de nodos
la; // el carácter actual en el string
void ukkadd(int c) { // agregar el carácter s al árbol
suff:; // volveremos aquí después de cada transición al sufijo (y agregaremos el carácter de nuevo)
if (r[tv]<tp) { // comprobar si aún estamos dentro de los bordes de la arista actual
// si no, encontrar la siguiente arista. Si no existe, crear una hoja y agregarla al árbol
if (t[tv][c]==-1) {t[tv][c]=ts;l[ts]=la;p[ts++]=tv;tv=s[tv];tp=r[tv]+1;goto suff;}
tv=t[tv][c];tp=l[tv];
} // de lo contrario simplemente pasar a la siguiente arista
if (tp==-1 || c==a[tp]-'a')
tp++; // si la letra de la arista es igual a c, bajar por esa arista
else {
// de lo contrario partir la arista en dos con el medio en el nodo ts
l[ts]=l[tv];r[ts]=tp-1;p[ts]=p[tv];t[ts][a[tp]-'a']=tv;
// agregar la hoja ts+1. Corresponde a la transición por c.
t[ts][c]=ts+1;l[ts+1]=la;p[ts+1]=ts;
// actualizar la información del nodo actual - recordar marcar ts como padre de tv
l[tv]=tp;p[tv]=ts;t[p[ts]][a[l[ts]]-'a']=ts;ts+=2;
// preparar el descenso
// tp marcará dónde estamos en el sufijo actual
tv=s[p[ts-2]];tp=l[ts-2];
// mientras el sufijo actual no haya terminado, descender
while (tp<=r[ts-2]) {tv=t[tv][a[tp]-'a'];tp+=r[tv]-l[tv]+1;}
// si estamos en un nodo, agregar un enlace de sufijo a él; de lo contrario agregar el enlace a ts
// (crearemos ts en la siguiente iteración).
if (tp==r[ts-2]+1) s[ts-2]=tv; else s[ts-2]=ts;
// agregar tp a la nueva arista y volver a agregar la letra al sufijo
tp=r[tv]-(tp-r[ts-2])+2;goto suff;
}
}
void build() {
ts=2;
tv=0;
tp=0;
fill(r,r+N,(int)a.size()-1);
// inicializar los datos de la raíz del árbol
s[0]=1;
l[0]=-1;
r[0]=-1;
l[1]=-1;
r[1]=-1;
memset (t, -1, sizeof t);
fill(t[1],t[1]+26,0);
// agregar el texto al árbol, letra por letra
for (la=0; la<(int)a.size(); ++la)
ukkadd (a[la]-'a');
}