T07
Condições de conclusão
Aberto: quinta-feira, 22 jul. 2021, 00:00
Vencimento: quinta-feira, 29 jul. 2021, 23:59
Resolva o Exercício 5.3.12, Suffix-prefix match, de S&W:
https://algs4.cs.princeton.edu/53substring/
O exercício é esse: queremos um algoritmo de tempo linear que resolve o seguinte problema:
Problema. Dadas duas cadeias de caracteres a e b, encontrar o sufixo mais longo de a que é prefixo de b.
Aqui, "tempo linear" significa tempo \(O(N + M)\), onde $N$ e $M$ são os comprimentos dos strings a e b. A constante de proporcionalidade na notação $O$ pode depender do tamanho do alfabeto.
Basta descrever o algoritmo pedido; não é necessário implementar. Naturalmente, para você se sentir seguro de que sua solução está correta, você pode implementar e testar seu programa, gerando instâncias interessantes :-).