Localizando todas as maneiras possíveis de inserir um padrão em uma sequência

Estou pensando nesse problema há um tempo e só consigo encontrar uma solução recursiva, mas sinto que há uma maneira de programação dinâmica para fazê-lo, mas não consigo descobrir. Esse é um problema famoso que eu não conheço?

P: Dada uma sequência e um padrão, retorne o número de maneiras exclusivas de corresponder as letras do padrão (em ordem) com a sequência.

Esclarecimento: Para encontrar uma correspondência, você pega o primeiro caractere do padrão, encontra o primeiro caractere correspondente na sequência e, em seguida, o segundo caractere do padrão e combina com o primeiro caractere correspondente da sequência APÓS a correspondência anterior personagem.

Exemplo 1 (4 correspondências):

String: DABBCDDE

Padrão: ABD

Maneiras possíveis (caracteres em negrito são onde o padrão é correspondido com a sequência):

D AB BC D DE
D A B B C D DE
D AB BCD D E
D A B B CD D E

Exemplo 2 (0 correspondências):

String: ABC

Padrão: BCA

(Você combina B, C e, no final da sequência, NÃO pode voltar e combinar com os caracteres anteriores)

Com a abordagem recursiva, eu tenho um método que monitora em qual índice estou na string ( sIndex ), bem como no padrão ( pIndex ). Se a string [sIndex] corresponde ao padrão [pIndex], chamamos o método novamente e aumentamos sIndex e pIndex. Caso contrário, aumente o sIndex e tente novamente para encontrar uma correspondência. O método retorna o número total porque o valor de retorno das chamadas recursivas é adicionado. (Correspondências adicionam 1, nenhuma correspondência adiciona 0)

Casos básicos:

Se pIndex for maior que o comprimento do padrão, retorne 0.
Se sIndex for maior que o comprimento da string, retorne 1 (encontramos uma correspondência!)

Que outras soluções existem?

algorithms recursion dynamic-programming Daniel Olsson
fonte

Valores duplicados são permitidos no padrão? Temos a garantia de que o padrão e a sequência estão em ordem?

Brandon Arnold

Sim, valores duplicados são permitidos no padrão. Não sei se me deixei claro demais, mas se você embaralhar a ordem, o problema mudará. Portanto, se você tiver CBA como sequência e o padrão for ABC, não haverá correspondências porque a primeira correspondência é A e, em seguida, não haverá mais caracteres na sequência para corresponder aos caracteres restantes no padrão (BC). Isso deixa claro?

11136 Daniel Olsson

Eu acho insertingbastante enganador. Não é esta a elementos correspondentes em patterncom elementos stringem ordem em todos os maneira possível?

Mai

Excluída a minha resposta regex, porque depois de jogar em js mexer eu descobri que não corresponde a todas as permutações possíveis :(

Gavin Clarke

Mai, isso é verdade, vou mudar a redação.

Daniel Olsson

Respostas:

Eu acho que você não precisa usar a Programação dinâmica para resolver isso. Eu acho que esta é a solução:

Primeiro faça a lista de listas para manter as ocorrências de caracteres no padrão no texto fornecido.
Vai ser assim

O diagrama a seguir:

   A    B    D 
             0 
   1 -> 2 -> 5
        3    6

Isso implica (assumindo a indexação 0) A ocorre na 0ª posição, B ocorre em 2,3 posições, D ocorre em 0,5,6 posições.
Para cada um dos pares de colunas consecutivas (aqui A, B e B, D) use ponteiros para mapear os valores correspondentes em uma coluna para os próximos valores maiores na próxima coluna. Aqui 1 (em col1) possui um ponteiro para 2 (em col2) e 2 (em col2) possui um ponteiro para 5 (em col3), pois 0 é menor que 2. 3 (em col2) possui um ponteiro para 5 (em col3) ) (Não pude desenhar aqui).
Para cada valor na primeira coluna, encontre o número de maneiras possíveis usando os ponteiros. Aqui 1 -> 2 e 2 -> 5 e, portanto, o número de maneiras possíveis é 2 * 2 maneiras (ou seja, 1-> 2-> 5, 1-> 2-> 6, 1-> 3-> 5, 1 -> 3-> 6). Você apenas precisa multiplicar o número de elementos restantes na coluna para cada valor de A.
Aqui apenas 1 valor para a Coluna1 (ou seja, A) está presente. Se houver várias colunas, calculamos o valor de cada valor de A usando os ponteiros e somamos todos eles para obter o número de maneiras.
Eu acho que a complexidade é O (n), como construir lista é O (n), ponteiros espaço e tempo de construção é O (n).

kaushalpranav
fonte

Isso está correto, mas você precisa ser mais específico sobre como gerar as ocorrências das letras padrão. A complexidade para isso é O (nm), em que n é o comprimento do padrão emm o comprimento do texto. (precisamos encontrar todas as ocorrências de cada letra no padrão).

Adrian Buzea 14/03