Para duas string A e B, definimos que a semelhança destas strings é o comprimento do prefixo que é comum a ambas. Por exemplo, a semelhança das strings abc
e abd
é 2, enquanto a semelhança das strings aaa
e aaab
é 3.
Calcule a soma de semelhanças de uma string S com cada um dos seus sufixos, incluindo a própria string como o primeiro sufixo.
Formato de Entrada:
A primeira linha contém o número de casos de testes T. Cada uma das T linhas próximas contém uma string cada.
Formato de Saída:
Exiba T linhas de saída, cada uma contendo um número inteiro que é para o caso de teste correspondente.
Premissas:
- 1 <= T <= 10
- As strings contém apenas caracteres minúsculos [a-z]
Exemplo de entrada:
2
ababaa
aa
Exemplo de saída:
11
3
Explicação:
Para o primeiro caso, os sufixos da string são ababaa
, babaa
, abaa
, baa
, aa
e a
. As semelhanças de cada uma dessas string com a string ababaa
são 6, 0, 3, 0, 1, 1 respectivamente. Assim a resposta é 6 + 0 + 3 + 0 + 1 + 1 = 11. Para o segundo caso a resposta é 2 + 1 = 3
Dúvidas
No resultado da comparação:
6 + 0 + 3 + 0 + 1 + 1 = 11
De onde sai o 0? Como é feita a comparação?
Por enquanto, tenho só a assinatura do método, que ficaria de esse jeito:
public static Integer semelhancaString(Integer n, String... strings) {}