Wyszukiwanie palindromów w ciągu znaków

Witam.
Mam taki problem: dany jest ciąg znaków np. mamacoścoścośamam.
Muszę napisać algorytm, który ma zwrócić MAMAcoścoścośAMAM, gdzie MAMAAMAM jest palindromem.
Inaczej mówiąc - algorytm wyszukuje równe połówki palindromów, które mogą być rozdzielone dowolnymi znakami (MAMA...AMAM, ale niedozwolone jest MAM...A...AMAM)

Czy ktoś może mnie nakierować? :)

Rozumiem że chodzi o wyszukanie najdłuższego takiego palindromu? A muszą być na krańcach ciągu czy XXXABCXXXCBAXXX też jest poprawne dla palindromu ABCCBA?

Dla ciągu literek xxxabcxxxcbaxxx odpowiedzią będzie xxxABCxxxCBAxxx. Połówki palindromu mogą być dowolnie umiejscowione.
Chodzi o wyszukanie wszystkich takich palindromów :)

Kawałek mojego kodu który nie zawsze robi to, o co jest proszony

package poligon;

import java.util.Scanner;

public class Sekwencje {
    private final String pierwotneSlowo;
    private String poTransformacji;
    private boolean[] transformacja;
    private final int dlugosc;
    
    public Sekwencje(String string) {
        pierwotneSlowo = string;
        poTransformacji = string;
        dlugosc = string.length();
        transformacja = new boolean[dlugosc];
        //zamianaLiterek();
    }
    
    private void zamianaLiterek() {
        poTransformacji = poTransformacji.replace('g', 'a'); //A == G
        poTransformacji = poTransformacji.replace('v', 'a'); //A == V
        poTransformacji = poTransformacji.replace('e', 'd'); //D == E
        poTransformacji = poTransformacji.replace('y', 'f'); //F == Y
        poTransformacji = poTransformacji.replace('q', 'n'); //N == Q
    }
    
    private void szukaniePalindromow(String szukane) {
        if(poTransformacji.contains(reverse(szukane))) {
            poTransformacji = poTransformacji.replaceAll(szukane, " "+szukane.toUpperCase()+" ");
            poTransformacji = poTransformacji.replaceAll(reverse(szukane), " "+reverse(szukane).toUpperCase()+" ");
        }
    }
    
    public void dzialaj() {
        for(int i = (dlugosc > 15)? 15 : dlugosc; i>2; i--)
            for(int j=0; j<dlugosc; j++)
                if(j+i <= dlugosc) {
                    String szukane = poTransformacji.substring(j, j+i).toLowerCase();
                    if(poTransformacji.contains(reverse(szukane))) {
                        poTransformacji = poTransformacji.replace(szukane, " "+szukane.toUpperCase()+" ");
                        poTransformacji = poTransformacji.replace(reverse(szukane), " "+reverse(szukane).toUpperCase()+" ");
                    }
                }
    }
    
    private String reverse(String string) {
        int length = string.length();
        StringBuilder zwracana = new StringBuilder(length);

        for(int i = length-1; i >= 0; i--)
            zwracana.append(string.charAt(i));

        return zwracana.toString();
    }
    
    @Override
    public String toString() {
        return poTransformacji;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Sekwencje sekwencje = new Sekwencje(scanner.nextLine()); //hkuhiewhsufgyuabjgvthgsfuygursfgsgtvgjbabgugfukygf
        sekwencje.dzialaj();
        System.out.println(sekwencje);
    }
}

Na krańcach w ten sposób:
Iteracja od początku i od końca ciągu z porównaniem aktualnej litery i ustawieniem flagi (czy takie same). Najdłuższy do tej pory zapisywany na boku.

Jeśli inaczej, to problem robi się bardziej skomplikowany.

EDIT: Too late... ;)

Ogólnie chodzi o szukanie sekwencji palindromów w aminokwasach, dlatego tam pojawia się "zamiana literek".
Mój kod trochę źle formułuje wyjście - jak już znajdziemy jakiś palindrom, to nie możemy tego łączyć ponownie

Odpowiedzią w moim kodzie dla takiego ciągu jest:
hkuhidwhs UFAFU ABJAAT hasf UFAU rsf ASA TAAJBA BA UAFU k FAF

A powinno być np.:
hkuhidwhsufafu ABJAAT hasf UFAU rsfasa TAAJBA ba UAFU kfaf

Możesz próbować usuwać każdy spójny podciąg z tekstu, a potem odpalać algorytm Manachera na całości. Złożoność to O(n^3).