Dada uma lista de strings, encontre cada par $(x,y)$ onde $x$ é uma subsequência de $y$.É possível fazer melhor que $O(n^2)$?

Question

Considere o seguinte problema algorítmico:Dada uma lista de strings $L = [s_1, s_2, \pontos, s_n]$, queremos conhecer todos os pares $(x,y)$ onde $x$ é uma subsequência de $y$.Podemos assumir que todas as strings têm comprimento máximo $m$, onde $m<<n$ e estão em um alfabeto finito $\Sigma$ com $|\Sigma| << n$.Também podemos assumir que o número de pares $(x,y)$ onde $x$ é uma subsequência de $y$ é muito menor que $n$.

Um algoritmo trivial seria este:

1. foreach x in L:
2.   foreach y in L:
3.      if x is subsequence of y:
4.         OUTPUT x,y

No entanto, isso tem complexidade $O(n^2\cdot m)$ - Estou curioso para saber se existe um algoritmo mais rápido (Mais rápido dado que o número de pares $(x,y)$ é muito menor que $n$, por exemplo, um algoritmo com complexidade dependendo do número de pares de saída).

Observe que esta pergunta é uma continuação de essa questão, que é quase o mesmo problema, mas para substrings (não subsequências).Pronto, o algoritmo Aho-Corasick resolveu meu problema perfeitamente - existe talvez algo assim, mas para subsequências?

Answer 1

Não, não é possível fazer melhor a menos que a Hipótese Forte do Tempo Exponencial (SETH) falhe.Se pudéssemos resolver este problema substancialmente mais rápido do que $O(n^2)$ obteríamos imediatamente um algoritmo muito mais rápido para resolver o problema NP-completo de Satisfatibilidade.Isto é verdade mesmo para $m$ um pouco mais do que $log(n)$ e o caso em que queremos decidir se tal par $(x,y)$ existe em tudo.

Veja, por exemplo, essas notas de aula na seção 3 "Limites inferiores rígidos para vetores ortogonais".A prova é análoga à prova do Teorema 2 nestas notas de aula.

Primeiro, consideramos o problema mais geral de dados dois conjuntos de strings $X,Y$, descobrindo se alguma string em $X$ é uma subsequência de uma string em $Y$.

Dada uma fórmula SAT, dividimos seu $n$ variáveis ​​em dois conjuntos iguais de $n/2$ variáveis.Em $\Sigma$ pegamos um caractere correspondente a cada cláusula.Em $X$ adicionamos uma string para cada atribuição possível à primeira metade das variáveis, com um caractere correspondente a cada cláusula não satisfeito por essas variáveis.Enquanto isso em $Y$, adicionamos uma string para cada atribuição à segunda metade das variáveis, com um caractere para cada cláusula satisfeita por essas variáveis.Claramente, a fórmula é satisfatória se e somente se alguma string em $X$ é uma subsequência de alguma string em $Y$.

Se este problema puder ser resolvido substancialmente mais rápido do que $O(n^2)$, então isso fornece um algoritmo substancialmente mais rápido para Satisfatibilidade do que $2^n$.Suponha que o problema possa ser resolvido em $O(n^{1,99})$ tempo, então a Satisfatibilidade poderia ser resolvida em $(2^{n/2})^{1,99}=O(2^{0,996n})$ o que contradiz SETH.

No seu problema, existe apenas um único conjunto de strings, todas elas podendo ser uma subsequência uma da outra.No entanto, isso não é um problema, pois podemos simplesmente modificar as strings em nossa instância de modo que nenhuma string $Y$ é uma subsequência de qualquer outra string (por exemplo, preenchendo todas as strings em $Y$ ter o mesmo comprimento) e preencher de forma semelhante cada string em $X$ com o mesmo comprimento que outras strings em $X$ (mas substancialmente mais curto que strings em $Y$).

Provavelmente, isso também pode ser feito com um alfabeto de tamanho constante (provavelmente até binário), mas requer uma codificação mais inteligente.