Witam!
Mam problem z implementacją algorytmu LCS według http://edu.i-lo.tarnow.pl/inf/alg/001_search/0056.php (ostatnia sekcja)
Wyłapuje on tylko pojedyncze wspólne litery
bool najkWspPodl(const char* s1, const char* s2, unsigned n, int& p1, int& p2, unsigned& lm) // s1 i s2 są długosci n, p1 -> pozycja lcs w s1, p2 -> --//-- w s2, lm -> długość lcs
{
int* l0 = new int[n];
int* l1 = new int[n];
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;
}
}
else
goto koniecPetli;
}
for (unsigned j = 0; j < n; j++)
l0[j] = l1[j];
koniecPetli:; // chyba szybciej tak niz boolem
}
delete[] l0;
delete[] l1;
cout << p1 << p2 << lm << endl;
return lm != 0;
}
I tak np. dla łańcuchów "kacper" i "perkac" wyświetla 3 0 1
Tak wgl to problemem jest sprawdzenie, czy 2 łańcuchy mozna zaprezentować jako XYZ i XZY, przy czym Y i Z są niepuste. Jakby ktoś miał lepszy pomysł jak to ogarnąć to pisać.