23.8.2016

foto Petr Bravenec

Petr Bravenec
+420 777 566 384
petr.bravenec@hobrasoft.cz

Odkazy

Wikipedia: Longest common substring problem
Stack Overflow: How to find Longest Common Substring using C++

Při práci na jednom z projektů jsem narazil na jednoduchou úlohu: z rozhlasového přijímače se odesílají informace o přijímané stanici. Úkolem je vypsat na displej jméno stanice. Potíž je v tom, že ve jméně přijímané stanice se mohou vyskytovat i informace o momentálně vysílané skladbě. Zatím pro zjednodušení předpokládám, že jménem stanice je nejdelší společný řetězec, který se v názvech vyskytuje (uvidím, jak se to bude chovat v praxi).

Vynalézat kolo mě už dávno nebaví. Mým první krokem proto byla návštěva u googlů. Tam mi sdělili, že problém je známý a má i vlastní stránku na Wikipedii a samozřejmě i na Stack Overflow.

Nalezený kód na Wikipedii je poněkud obtížně čitelný. Odkaz na Stack Overflow se sice ptá na implementaci v C++, odpovědi se však C++ netýkají. Kód v Javě se však dal přepsat do C++ bez potíží. Zájemci níže naleznou algoritmus přepsaný pro C++ a knihovnu Qt.

Implementace Longest Common String algoritmu v C++ a Qt

Download

QString longestCommonString(const QString& str1, const QString& str2) {
    #define MAX(x,y) ( (x>y) ? x : y )
    #define INDEX(x,y) ((x)+((str2size)+1)*(y))
    int str1size = str1.size();
    int str2size = str2.size();
    int *longest = new int[(str1size+1)*(str2size+1)];
    int min_index = 0;
    int max_index = 0;

    for (int i=0; i < str1size + 1; i++) {
        longest[INDEX(0,i)]=0;
        }

    for (int i=0; i < str2size + 1; i++) {
        longest[INDEX(i,0)]=0;
        }

    for (int i=0; i<str2size; i++) {
        for (int j=0; j<str1size; j++) {
            int tmp_min = j;
            int tmp_max = j;
            int tmp_offset = 0;
            if (str2[i] == str1[j]) {
                while (tmp_offset <= i && tmp_offset <= j &&
                       str2[i-tmp_offset] == str1[j-tmp_offset]) {
                    tmp_min -= 1;
                    tmp_offset += 1;
                    }
                }

            tmp_min += 1;
            int length = tmp_max - tmp_min + 1;
            int tmp_max_length = MAX(longest[INDEX(i,j)], 
                                    MAX(longest[INDEX(i+1,j)], 
                                    longest[INDEX(i,j+1)]));
            if (length > tmp_max_length) {
                min_index = tmp_min;
                max_index = tmp_max;
                longest[INDEX(i+1,j+1)] = length;
              } else {
                longest[INDEX(i+1,j+1)] = tmp_max_length;
                }
            }
        }

    delete longest;
    return str1.mid(
            min_index, 
            ((max_index >= str1size-1) ? str1size : max_index + 1) - min_index 
            );
}
Hobrasoft s.r.o. | Kontakt