Т.е. у этой задачи предполагается написание перебора с отсечениями? Последовательно добавляем символы в конец строки и если не смогли найти палиндрома, который бы являлся суффиксом новой строки, то дальше не перебираем?