Encontrando todas as subsequências do dicionário - algoritmo

Em um programa, preciso responder de forma eficiente às consultas do seguinte formato:

Dado um conjunto de strings A e uma string de consulta q retorna todos os s ∈ A tais que s é uma subsequência de q Por exemplo, dado A = {"abc", "aaa", "abd"} e q = "abcd", "abc" e "abd" devem ser retornados.

Existe alguma maneira melhor do que iterar cada elemento de A e verificar se é uma subsequência de q?

NOTA: Eu tenho planejador STRIPS ou planejador automatizado em mente. Cada estado no planejador STRIPS é um conjunto de proposições como {"(room rooma)", "(at-robby rooma)", "(na ball1 rooma)"}. Eu quero encontrar todas as ações básicas aplicáveis ​​a um determinado estado. Ações no planejador STRIPS consistem basicamente em duas partes, pré-condições e efeitos (que não são realmente relevantes aqui). Pré-condições são conjuntos de proposições necessárias para serem verdadeiras para aplicar uma ação a um estado. Por exemplo, para aplicar uma ação "(mover rooma roomb)", suas pré-condições, {"(room rooma)", "(sala roomb)", "(at-robby rooma)"} devem ser todas verdadeiras no estado.

Respostas:

Se o seu conjunto UMA é grande e você tem muitas consultas, você poderia implementar um estrutura trie-like, onde nível n refere-se ao personagem n em uma string. No seu exemplo:

trie = {
a: {
a: {
a: { value: "aaa"}
},
b {
c: { value: "abc"},
d: { value: "abd"}
}
}
}

Isso permitiria que você procurasse correspondências em um caminho bifurcado pelo trie:

function query(trie, q) {
s = Set();

if (q.isEmpty()) {
if (trie.value) s.add(t.value);
} else {
s = s.union(query(trie, q[1:]));

c = substr(q, 0, 1);
if (t[c]) {
s = s.union(query(t[c], substr(q, 1));
}
}
return s;
}

Efetivamente, você irá gerar todos os 2 ^m subconjuntos da cadeia de quesy de m caracteres, mas na prática, o trie é esparso e você acaba verificando menos caminhos.

O ganho de velocidade vem com muitas pesquisas. Construir o trio é mais caro do que fazer uma pesquisa de força bruta. Mas se você construir o trie apenas um ou tiver um meio de atualizar o trie quando você atualizar o conjunto UMA, você terá um bom desempenho de pesquisa.

A estrutura de dados real para os nós triedepende de quantos elementos possíveis os itens podem ter. No seu exemplo, apenas quatro letras são usadas. Se você tiver um intervalo limitado de "letras", poderá usar uma matriz. Caso contrário, você pode precisar de um tipo de dicionário, o que pode tornar a árvore bastante grande na memória.