XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: subsequencias.x, onde x deve ser c, cpp, java, js ou py

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
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação