23.8.2016
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.
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
);
}