Nota: En este artículo, los índices de cadena comienzan desde \(1\).

Consideremos primero un problema sencillo:

Dada una cadena \(S\), encontrar la longitud de la mayor frontera común entre dos prefijos de \(S\) de longitudes \(n\) y \(m\).

A: ¡Solución por fuerza bruta!

\(1\le n,m\le |S|\le 10^6\).

A: ¡Añado una función hash!

\(T\) consultas, \(T\le 10^5\).

A: ...

Aquí es donde entra nuestro árbol de fallas.

Veamos un ejemplo concreto:

Supongamos que tenemos dos prefijos de una cadena. Podemos observar que su mayor frontera común tiene longitud \(3\).

Al hablar de fronteras, ¿cómo no mencionar el algoritmo KMP? Dado que ambas cadenas son prefijos de la misma cadena, una de ellas (la más corta)必定 es también un prefijo de la otra (la más larga).

Ahora, mostremos los índices de caracteres de la cadena más larga junto con su array \(\text{falla}\).

\(\begin{array}{c|lcr} Índice & \text{falla} \\ \hline 1 & 0\\ 2 & 0\\ 3 & 1\\ 4 & 2\\ 5 & 3\\ 6 & 4\\ \end{array}\)

¿Puede observar algo? ¿No? ¿Qué tal si construimos un árbol?

A continuación, conectamos los bordes \((\text{falla}[i],i),i\in[1,6]\).

Obtenemos esta estructura:

La mayor frontera común entre los sufijos de longitud \(4\) y \(6\) es \(2\), ¿cuál es su relación en el árbol?

Se observa que \(2\) es el ancestro común más bajo (LCA) de \(4\) y \(6\) (excluyéndose a sí mismos).

Este árbol es lo que se conoce como árbol de fallas. Al construir este árbol para una cadena, podemos rápidmaente encontrar la mayor frontera común entre múltiples pares de prefijos de diferentes longitudes.

Explicación del principio:

Si \(C\) es una frontera de \(B\), y \(B\) es una frontera de \(A\), entonces \(C\) también es una frontera de \(A\).

Es decir, después de procesar el array \(\text{falla}\), podemos saltar de \(A\) a \(B\) mediante saltos \(\text{falla}\), y de \(B\) a \(C\) de manera similar.

Por lo tanto, si dos prefijos pueden saltar a la misma posición mediante saltos \(\text{falla}\), la primera posición común a la que llegan es su mayor frontera común.

Este proceso es similar a cómo encontramos el LCA en un árbol, por lo que podemos construir una estructura de árbol y utilizar métodos como el aumento binario o la descomposición de árboles para realizar los saltos.

Implementación con aumento binario:

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1000100
#define rr register 
#define INF 0x3f3f3f3f

using namespace std;

char cadena[maxn];
int m,n,j,total,falla[maxn][40];
int prox[maxn],cabeza[maxn],profundidad[maxn];
struct arista{int inicio,fin,sig;}e[maxn];

int leer(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

void agregar(int inicio, int fin){
    e[++total]=(arista){inicio,fin,cabeza[inicio]};cabeza[inicio]=total;
}

int dfs(int u){
    for(rr int i=1;i<=21;i++)
        falla[u][i]=falla[falla[u][i-1]][i-1];
    for(rr int i=cabeza[u];i;i=e[i].sig){
        int v=e[i].fin;
        profundidad[v]=profundidad[u]+1;
        falla[v][0]=u;
        dfs(v);
    }
}

int obtenerLCA(int x, int y){
    if(profundidad[x]<profundidad[y]) swap(x,y);
    for(rr int i=21;i>=0;i--)
        if(profundidad[falla[x][i]]>=profundidad[y])x=falla[x][i]; 
    for(rr int i=21;i>=0;i--)
        if(falla[x][i]!=falla[y][i])x=falla[x][i],y=falla[y][i];    
    return falla[x][0];
}

int main(){
    scanf("%s",cadena+1);n=strlen(cadena+1);
    for(rr int i=1;i<n;i++){
        while(j&&cadena[j+1]!=cadena[i+1]) j=prox[j];
        if(cadena[j+1]==cadena[i+1]) j++,prox[i+1]=j;
    }
    for(rr int i=1;i<=n;i++) agregar(prox[i],i);
    dfs(0);m=leer();
    for(rr int i=1,fr,to;i<=m;i++){
        fr=leer();to=leer();
        printf("%d\n",obtenerLCA(fr,to));
    }
    return 0;
}

Implementación con descomposición de árboles:

#include<queue>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1000100
#define rr register 
#define INF 0x3f3f3f3f

using namespace std;

char cadena[maxn];
int m,n,j,total;
int prox[maxn],cabeza[maxn];
struct arista{int inicio,fin,sig;}e[maxn];

int leer(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

void agregar(int inicio, int fin){
    e[++total]=(arista){inicio,fin,cabeza[inicio]};cabeza[inicio]=total;
}

namespace Descomposicion{
    int tamano[maxn],profundidad[maxn];
    int padre[maxn],hijo_pesado[maxn],cima[maxn];
    void dfs1(int u, int p){
        profundidad[u]=profundidad[p]+1;
        tamano[u]=1;padre[u]=p;
        for(rr int i=cabeza[u];i;i=e[i].sig){
            int v=e[i].fin;
            if(v==p) continue;
            dfs1(v,u);tamano[u]+=tamano[v];
            if(tamano[hijo_pesado[u]]<tamano[v]) hijo_pesado[u]=v;
        }
    } 
    
    void dfs2(int u, int cp){
        cima[u]=cp;
        if(hijo_pesado[u]!=n+5) dfs2(hijo_pesado[u],cp);
        for(rr int i=cabeza[u];i;i=e[i].sig){
            int v=e[i].fin;
            if(v==hijo_pesado[u]||v==padre[u]) continue;
            dfs2(v,v);
        }
    }
    
    int obtenerLCA(int x, int y){
        int primero=x,segundo=y,resultado;
        while(cima[x]!=cima[y]){
            if(profundidad[cima[x]]<profundidad[cima[y]]) swap(x,y);
            x=padre[cima[x]];
        }
        resultado=profundidad[x]<profundidad[y]?x:y;
        if(resultado==primero||resultado==segundo) return padre[resultado];
    }
}

int main(){
    scanf("%s",cadena+1);n=strlen(cadena+1);
    for(rr int i=1;i<n;i++){
        while(j&&cadena[j+1]!=cadena[i+1]) j=prox[j];
        if(cadena[j+1]==cadena[i+1]) j++,prox[i+1]=j;
    }
    for(rr int i=0;i<=n;i++) Descomposicion::hijo_pesado[i]=n+5;
    for(rr int i=1;i<=n;i++) agregar(prox[i],i);
    Descomposicion::dfs1(0,-1);Descomposicion::dfs2(0,0);
    
    m=leer();
    for(rr int i=1,fr,to;i<=m;i++){
        fr=leer();to=leer();
        printf("%d\n",Descomposicion::obtenerLCA(fr,to));
    }
    return 0;
}