Subsequência
Por OBI - Olimpíada Brasileira de Informática 2006 
Brazil
Por OBI - Olimpíada Brasileira de Informática 2006 Brazil
Uma subsequência de uma sequência de caracteres 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 S2 se, dada qualquer subsequência de tamanho N de S1, não ´e 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 independência de S1 em relação a S2.
A entrada contém 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 S1 (1 ≤ N ≤ 2000) e o comprimento da sequência S2 (1 ≤ M ≤ 2000). 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’). As sequências possuem no máximo 2000 caracteres. Sempre existe uma solução para os casos de teste fornecidos.
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.
| Exemplos de Entrada | Exemplos de Saída |
|
5 5 cbbca ccabc |
2 |
|
10 5 ababaaaaaa ababa |
4 |
|
10 11 bcbcccacab baaabcbaaca |
3 |