Em um programa eu preciso responder eficientemente as perguntas do seguinte formulário:

Dado um conjunto de cordasA e uma string de consultaq devolver tudos ∈ A tal que q é umsubsequência dos

Por exemplo, dadoA = {"abcdef", "aaaaaa", "ddca"} eq = "acd" exatamente"abcdef" deve ser devolvido.

O seguinte é o que eu considerei considerado até agora:

Para cada caractere possível, faça uma lista ordenada de todas as cadeias / locais onde aparece. Para consultar, intercalar as listas dos caracteres envolvidos e digitalizá-los procurando correspondências dentro dos limites das strings.

Isso provavelmente seria mais eficiente para palavras em vez de caracteres, já que o número limitado de caracteres diferentes tornará as listas de retorno muito densas.

Para cada n-prefixoq pode ter, armazene a lista de todas as strings correspondentes.n pode realisticamente estar perto de 3. Para as strings de consulta mais longas que a brute force a lista inicial.

Isso pode acelerar um pouco as coisas, mas pode-se facilmente imaginar algumas n-subsequências presentes perto de todas as strings emA, o que significa pior caso é o mesmo que apenas brute forçando todo o conjunto.

Você conhece alguma estrutura de dados, algoritmos ou truques de pré-processamento que possam ser úteis para executar a tarefa acima com eficiência para grandesAs? (Minhasss terá cerca de 100 caracteres)

Atualizar: Algumas pessoas sugeriram usar o LCS para verificar seq é uma subsequência des. Eu só quero lembrar que isso pode ser feito usando uma função simples, como:

def isSub(q,s):
  i, j = 0, 0
  while i != len(q) and j != len(s):
    if q[i] == s[j]:
      i += 1
      j += 1
    else:
      j += 1
  return i == len(q)

Atualização 2: Fui convidado a dar mais detalhes sobre a natureza doq, A e seus elementos. Embora prefira algo que funcione da maneira mais geral possível, presumoA terá comprimento em torno de 10 ^ 6 e precisará suportar a inserção. Os elementoss será mais curto com uma duração média de 64. As consultasq terá apenas 1 a 20 caracteres e será usado para uma pesquisa ao vivo, então a consulta "ab" será enviada logo antes da consulta "abc". Mais uma vez, prefiro muito mais que a solução use o acima o mínimo possível.

Atualização 3: Ocorreu-me que uma estrutura de dados comO(n^{1-epsilon}) pesquisas, permitir-lhe-ia resolver o OVP / refutar a conjectura de SETH. Essa é provavelmente a razão do nosso sofrimento. As únicas opções são, então, refutar a conjectura, usar aproximação ou tirar proveito do conjunto de dados. Eu imagino quadlets e tentativas faria o último em diferentes configurações.