Самая длинная общая подстрока из более чем двух строк

Мне нужно вычислить самые длинные общие подстроки из набора имен файлов в C ++.

Точно, у меня есть std :: список std :: strings (или эквивалент QT, тоже хорошо)

char const *x[] = {"FirstFileWord.xls", "SecondFileBlue.xls", "ThirdFileWhite.xls", "ForthFileGreen.xls"};
std::list<std::string> files(x, x + sizeof(x) / sizeof(*x));

Мне нужно вычислить n различных длинных общих подстрок всех строк, в этом случае, например, для n = 2

 "File" and ".xls"

Если бы я мог вычислить самую длинную общую подпоследовательность, я мог бы вырезать ее и запустить алгоритм снова, чтобы получить второе самое длинное, так что по сути это сводится к:

Существует ли (эталонная?) Реализация для вычисления LCS из std :: list из std :: strings?


Это не хороший ответ, но грязное решение, которое у меня есть — грубая сила в QList из QUrls, из которого берется только часть после последней «/». Я хотел бы заменить это «правильным» кодом.

(Я обнаружил http://www.icir.org/christian/libstree/ — это очень помогло бы, но я не могу заставить его скомпилировать на моей машине. Кто-то использовал это может быть?)

QString SubstringMatching::getMatchPattern(QList<QUrl> urls)
{
QString a;

int foundPosition = -1;
int foundLength = -1;
for (int i=urls.first().toString().lastIndexOf("/")+1; i<urls.first().toString().length(); i++)
{
bool hit=true;
int xj;
for (int j=0; j<urls.first().toString().length()-i+1; j++ ) // try to match from position i up to the end of the string :: test character at pos. (i+j)
{
if (!hit) break;

QString firstString = urls.first().toString().right( urls.first().toString().length()-i ).left( j ); // this needs to match all k strings
//qDebug() << "SEARCH " << firstString;

for (int k=1; k<urls.length(); k++) // test all other strings, k = test string number
{
if (!hit) break;

//qDebug() << " IN  " << urls.at(k).toString().right(urls.at(k).toString().length() - urls.at(k).toString().lastIndexOf("/")+1);
//qDebug() << " RES " << urls.at(k).toString().indexOf(firstString, urls.at(k).toString().lastIndexOf("/")+1);
if (urls.at(k).toString().indexOf(firstString, urls.at(k).toString().lastIndexOf("/")+1)<0) {
xj = j;
//qDebug() << "HIT LENGTH " << xj-1 << " : " << firstString;
hit = false;
}
}

}
if (hit) xj = urls.first().toString().length()-i+1; // hit up to the end of the string
if ((xj-2)>foundLength) // have longer match than existing, j=1 is match length
{
foundPosition = i; // at the current position
foundLength = xj-1;
//qDebug() << "Found at " << i << " length " << foundLength;
}
}

a = urls.first().toString().right( urls.first().toString().length()-foundPosition ).left( foundLength );
//qDebug() << a;
return a;
}

4

Решение

Если, как вы говорите, суффиксные деревья слишком тяжеловесны или неосуществимы,
достаточно простой подход грубой силы может быть адекватным для вашего приложения.

Я предполагаю, что различные подстроки не должны перекрываться и выбираются из
слева направо.

Даже с этими предположениями не должно быть уникального набора, который включает
« N отдельные самые длинные общие подстроки «из набора строк. N является,
там может быть больше, чем N отдельные общие подстроки все одинаковые максимальные
длина и любой выбор N из них было бы произвольно. Соответственно
решение находит самое большее N * наборы * самого длинного отчетливого общего
подстроки, в которых все те же длины имеют один набор.

Алгоритм выглядит следующим образом:

  • Q целевая квота длин.

  • Струны это проблемный набор строк.

  • Результаты изначально пустая мультикарта, которая отображает длину на набор строк,
    Результаты [л] быть набором с длиной L

  • N, изначально 0, это число различных длин, представленных в Результаты

  • Если Q это 0 или Струны пустой возврат Результаты

  • Найти любой самый короткий член Струны; сохранить копию этого S и удали это
    от Струны. Мы продолжаем сравнивать подстроки S с этими
    из Струны потому что все общие подстроки {Струны, S} должно быть
    подстроки S.

  • Итеративно генерировать все подстроки S, самый длинный сначала, используя
    очевидный вложенный цикл, контролируемый смещением и длиной. Для каждой подстроки сс из
    S:

    • Если сс не является общей подстрокой Струны, следующий.

    • Перебрать Результаты [л] за L > = длина сс до конца
      Результаты или до сс оказывается подстрокой исследуемого
      результат. В последнем случае, сс уже не отличается от результата
      в руке, так что дальше.

    • сс является обычной подстрокой, отличной от любой уже имеющейся в наличии. Перебрать
      Результаты [л] за L < длина сс, удаляя каждый результат, который является
      подстрока из сс, потому что все они короче сс и не отличается
      от него. сс теперь общая подстрока, отличная от любой уже имеющейся
      все остальные, которые остаются в руках, отличаются от сс.

    • За L = длина сс, проверить, Результаты [л] существует, т.е. если
      есть какие-то результаты в руке той же длины, что и сс. Если нет, назовите это
      NewLength состояние.

    • Проверьте также, если N == Q, то есть мы уже достигли целевой квоты
      длины. Если NewLength получает, а также N == Q, называть это StickOrRaise состояние.

    • Если StickOrRaise получает затем сравнить длину сс с L =
      Длина кратчайших результатов в руке. Если сс короче чем L
      тогда это слишком мало для нашей квоты, так что дальше. Если сс длиннее чем L
      тогда все кратчайшие результаты должны быть вытеснены в пользу сс, так удали
      Результаты [л] и декремент N.

    • Вставить сс в Результаты под ключ его длиной.

    • Если NewLength получает, приращение N.

    • Отказаться от внутренней итерации по подстрокам S которые имеют
      такое же смещение сс но короче, потому что ни один из них не отличается
      от сс.

    • Переместить смещение в S для внешней итерации по длине сс,
      к началу следующей неперекрывающейся подстроки.

  • Вернуть Результаты.

Вот программа, которая реализует решение и демонстрирует его с
список строк:

#include <list>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

// Get a non-const iterator to the shortest string in a list
list<string>::iterator shortest_of(list<string> & strings)
{
auto where = strings.end();
size_t min_len = size_t(-1);
for (auto i = strings.begin(); i != strings.end(); ++i) {
if (i->size() < min_len) {
where = i;
min_len = i->size();
}
}
return where;
}

// Say whether a string is a common substring of a list of strings
bool
is_common_substring_of(
string const & candidate, list<string> const & strings)
{
for (string const & s : strings) {
if (s.find(candidate) == string::npos) {
return false;
}
}
return true;
}/* Get a multimap whose keys are the at-most `quota` greatest
lengths of common substrings of the list of strings `strings`, each key
multi-mapped to the set of common substrings of that length.
*/
multimap<size_t,string>
n_longest_common_substring_sets(list<string> & strings, unsigned quota)
{
size_t nlengths = 0;
multimap<size_t,string> results;
if (quota == 0) {
return results;
}
auto shortest_i = shortest_of(strings);
if (shortest_i == strings.end()) {
return results;
}
string shortest = *shortest_i;
strings.erase(shortest_i);
for ( size_t start = 0; start < shortest.size();) {
size_t skip = 1;
for (size_t len = shortest.size(); len > 0; --len) {
string subs = shortest.substr(start,len);
if (!is_common_substring_of(subs,strings)) {
continue;
}
auto i = results.lower_bound(subs.size());
for (   ;i != results.end() &&
i->second.find(subs) == string::npos; ++i) {}
if (i != results.end()) {
continue;
}
for (i = results.begin();
i != results.end() && i->first < subs.size(); ) {
if (subs.find(i->second) != string::npos) {
i = results.erase(i);
} else {
++i;
}
}
auto hint = results.lower_bound(subs.size());
bool new_len = hint == results.end() || hint->first != subs.size();
if (new_len && nlengths == quota) {
size_t min_len = results.begin()->first;
if (min_len > subs.size()) {
continue;
}
results.erase(min_len);
--nlengths;
}
nlengths += new_len;
results.emplace_hint(hint,subs.size(),subs);
len = 1;
skip = subs.size();
}
start += skip;
}
return results;
}

// Testing ...

int main()
{
list<string> strings{
"OfBitWordFirstFileWordZ.xls",
"SecondZWordBitWordOfFileBlue.xls",
"ThirdFileZBitWordWhiteOfWord.xls",
"WordFourthWordFileBitGreenZOf.xls"};

auto results = n_longest_common_substring_sets(strings,4);
for (auto const & val : results) {
cout << "length: " << val.first
<< ", substring: " << val.second << endl;
}
return 0;
}

Выход:

length: 1, substring: Z
length: 2, substring: Of
length: 3, substring: Bit
length: 4, substring: .xls
length: 4, substring: File
length: 4, substring: Word

(Построен с gcc 4.8.1)

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]