URI Online Judge | 2320

Subsequência

Por OBI - Olimpíada Brasileira de Informática 2006 BR Brazil

Timelimit: 1

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.

Entrada

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.

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.

Exemplos de Entrada Exemplos de Saída

5 5
cbbca
ccabc

2

10 5
ababaaaaaa
ababa

4

10 11
bcbcccacab
baaabcbaaca

3