Dwa łańcuchy jako XYZ i XZY - C++

Witam!

Mam dwa łańcuchy. Potrzebuję sprawdzić, czy można je zaprezentować jako XYZ i XZY, przy czym Y i Z są niepuste.
Przykładowo, "kacper" i "perkac" lub "ababbabaab" i "abaaabbbab" są takimi łańcuchami.

Mój pomysł to 'zjedzenie' takiego samego początku obu łańcuchów (o ile taki jest), a potem wyszukiwanie LCS (najdłuższego wspólnego podłańcucha) reszty i sprawdzanie czy to, co zostało jest takie same.
Mam problem z implementacją tego LCS - zwraca tylko pojedyńczy wspólny znak. Używam algorytmu http://edu.i-lo.tarnow.pl/inf/alg/001_search/0056.php, ostatnia sekcja. Wszystkie angielskie algorytmy mają złożoność pamięciową O(mn), a ten ma O(n), a zależy mi na pamięci.

bool najkWspPodl(const string& s1, const string& s2, int& p1, int& p2, unsigned& lm) // s1 i s2 są tej samej długosci, p1 -> pozycja lcs w s1, p2 -> --//-- w s2, lm -> długość lcs
{    
    unsigned n = s1.size();
    //int* l0 = new int[n];
    //int* l1 = new int[n];
    vector<int> l0(n, 0), l1(n); // hmm, RAII jest, ale poco?
 
    //for (unsigned i = 0; i < n; i++)
    //    l0[i] = 0;
    lm = 0;
 
    for (unsigned i = 0; i < n; i++)
    {
        for (unsigned j = 0; j < n; j++)
        {
            if (s1[i] == s2[j])
            {
                l1[j + 1] = 1 + l0[j];
                if (l1[j + 1] > lm)
                {
                    lm = l1[j + 1];
                    p1 = i - lm + 1;
                    p2 = j - lm + 1;
                }
                else
                {
                    l1[j + 1] = 0;
                    goto koniecPetli; // ała, ale szybciej tak, niż boolem
                }
            }
            else
                goto koniecPetli;
        }
        for (unsigned j = 0; j < n; j++)
            l0[j] = l1[j];
 
    koniecPetli:;
    }
 
    //delete[] l0;
    //delete[] l1;
    return lm != 0;
}

Od biedy ujdzie też regex "(.*)(.+)(.+)\1\3\2". Ale to nie będzie zbyt szybkie.
Poza tym, na moim komputerze (Windows, MSVC) działa, ale na Linuxie (GCC) wyrzuca SIGSEGV.

Jakby ktoś miał jeszcze jakieś lepsze pomysły to pisać.

Czy dobrze rozumiem, ty masz stwierdzić tylko czy dwa ciągi pasują do siebie. Nie ma sz warunku optymalizacyjnego typu "znajdź najkrótsze X".
Jeśli tak to LCS zupełnie tu nie pasuje.

A metoda jest prosta. Iterujesz po długości X <0..n-2), sprawdzasz czyX=X', a następnie bierzesz pierwszą literę z Y i ostatnią z Z, łączysz w parę i wyszukujesz w Z'Y'. To pozwala ci na szybkie wyznaczenie potencjalnej granicy między Y i Z (warunek konieczny), na tej podstawie sprawdzasz czy X=X' i Y=Y (warunek wystarczający).
Jeśli do siebie wyszukujesz dalej parę liter i znowu sprawdzasz warunek wystarczający, jeśli para liter nie występuje to kontynuujesz iterację po długości X.
Jeśli nic się nie znajdzie zwracasz fałsz.

Wychodzi złożoność obliczeniowa o(n³) - iteracja po długości X * wyszukanie pary liter * sprawdzenie dopasowania Y Z.

No to złożoność kwadratowa:
Początek jak wyżej: iterujesz po długości X i sprawdzasz czy X=X'. Następnie zostaje potencjalne YZ w pierwszym stringu i ZY w drugim. Teraz zauważamy, że ZY to obrót YZ, więc z pierwszego stringa łączymy YZ ze sobą i otrzymujemy YZYZ, a następnie sprawdzamy, czy ZY z drugiego jest podciągiem YZYZ (co możemy zrobić liniowo algorytmem KNP). Następnie pozostaje ustalić postać Y i Z, ale to jest proste, bo jeżeli wiemy, że ZY jest w YZYZ, to znamy jego pozycję, więc wszystko przed wystąpieniem ZY jest postaci Y, a wszystko po wystąpieniu ZY jest postaci Z.
Pozostaje jeszcze sprawdzenie, czy Y lub Z są puste, ale to już jest proste.