UVA 11475 Rodrigo Paes Algoritmo de String Matching Knuth-Morris-Pratt's (KMP) - usado para palindromo Seja s a string dada. Suponha que s = r.p onde . = concatenação p é um palíndromo Mas pode ser que s não seja um palíndromo. Então queremos: s' = r.p.reverso(r) Logo, s' é um palíndromo. Para adicionar o menor número de letras possível, queremos p o maior possível e, consequentemente, r o menor possível. Mas não sabemos como encontrar p. Entretanto, sabemos que o kmp nos dá o maior sufixo que também é prefixo. Logo, se p estivesse no começo da string e no final, poderíamos encontrá-lo com o kmp. Além disso, não podemos esquecer que p é palídromo. Considere então que: s'' = reverso(s).'#'.s Logo, s'' também seria um palíndromo. s'' = reverso(r.p).'#'.r.p s'' = p.reverso(r).'#'.r.p , como p é palíndromo, o reverso dele é ele mesmo. Agora p está no início e no fim. Portanto, se rodarmos o kmp em s'', encontraremos exatamente o maior p. Para isso, precisaremos pegar o último valor da tabela de falhas do kmp, pois o último valor, nos dará o tamanho do maior sufixo que também é prefixo e que está no final e no início de s'', e não no meio. Conhecendo o p, e sabendo que reverso(s)= p.reverso(r), temos como descobrir quem é o reverso(r). Para isso, basta pegar a substring de: substring( length(s) - length(p), length(s)-1 ). Com esses dois valores, agora podemos montar a resposta que queremos, que é justamente s': s' = r.p.reverso(r) s' = s.reverso(r) Exemplo: s = 'ababb' reverso(s) = 'bbaba' s'' = reverso(s).'#'.s s'' = 'bbaba#ababb' Construindo a failure_table em s'': failure_table = -1 0 1 0 1 0 0 0 1 0 1 2 Logo, o maior sufixo que tem tamanho 2, ou seja, ele é o bb Com isso, sabemos que reverso(r) = substring(bbaba, 2,4) = aba Logo, a solução será: s' = s.reverso(r) s' = 'ababb'.'aba' s' = 'ababbaba'