Kłopoty z implementacją algorytmu wyszukiwania najdłuzszego podłańcucha
Ostatnio zmodyfikowano 2015-06-22 16:30
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 bool najkWspPodl( const char * s1, const char * s2, unsigned n, int & p1, int & p2, unsigned & lm ) { 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:; } 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ć. |
|
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". |
|
« 1 » |