Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Kłopoty z implementacją algorytmu wyszukiwania najdłuzszego podłańcucha

Ostatnio zmodyfikowano 2015-06-22 16:30
Autor Wiadomość
kubawal
Temat założony przez niniejszego użytkownika
Kłopoty z implementacją algorytmu wyszukiwania najdłuzszego podłańcucha
» 2015-06-20 20:49:16
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

C/C++
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 można zaprezentować jako XYZ i XZY, przy czym Y i Z są niepuste. Jakby ktoś miał lepszy pomysł jak to ogarnąć to pisać.
P-133857
kubawal
Temat założony przez niniejszego użytkownika
» 2015-06-22 16:30:53
Dobra, problem rozwiązany za pomocą regexa "(.*)(.+)(.+)\\1\\3\\2".
P-133929
« 1 »
  Strona 1 z 1