T07
Requisitos de finalización
Apertura: jueves, 22 de julio de 2021, 00:00
Cierre: jueves, 29 de julio de 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 :-).