Subsequências
Uma subsequência de uma sequência de caractere S é definida como uma sequência de caracteres de S, não necessariamente consecutivos, na mesma ordem em que eles ocorrem na sequência original.
Dadas duas sequências de caracteres S1 e S2 dizemos que S1 possui grau N de independência em relação a S2se, dada qualquer subsequência de tamanho N de S1, não é possível formar tal subsequência a partir de S2 Por exemplo, o grau de independência da sequência S1 =‘ababaa’ em relação á sequência S2=‘abbaa’ é igual a 3, pois todas as subsequências de S1 de tamanho 1 (‘a’, ‘b’) e todas as subsequências de tamanho 2 (‘aa’, ‘ab’, ‘ba’, ‘bb’) podem ser formadas a partir de S2 mas a subsequência ‘bab’, de tamanho 3, não pode ser formada a partir de S2.
Escreva um programa que, dadas duas sequências S1 e S2 determine o grau N de independencia de S1 em relação a S2.
Entrada
A entrada conté um único conjunto de testes, que deve ser lido do dispositivo de entrada padráo (normalmente o teclado). A entrada contém três linhas. A primeira linha contém dois inteiros N e M que indicam respectivamente o comprimento da sequência e o comprimento da sequência. A segunda linha contém a sequência S1 e a terceira linha contém a sequência S2 As sequências são formadas somente pelas letras minúsculas sem acento (‘a’ - ‘z’). Sempre existe uma solução para os casos de teste fornecidos.
Saída
Seu programa deve imprimir, na saída padrão, uma única linha, contendo o grau N de indepedência de S1 em relação a S2.
Restrições
- 1 ≤ N ≤ 2000
- 1 ≤ M ≤ 2000
Exemplos
Entrada
ababaa abbaa |
Saída
3 |
Entrada
babab babba |
Saída
3 |
Entrada
banana anbnaanbaan |
Saída
5 |
