Идеи оптимизации — самая длинная общая подстрока

Question

Идеи оптимизации — самая длинная общая подстрока

У меня есть эта программа, которая должна найти самую длинную общую подстроку из ряда строк. Что и происходит, но если строки очень длинные (т. Е.> 8000 символов), это работает медленно (1,5 секунды).
Есть ли способ оптимизировать это?

Программа такая:

//#include "stdafx.h"#include <iostream>
#include <string>
#include <vector>
#include <cassert>using namespace std;

const unsigned short MAX_STRINGS = 10;
const unsigned int  MAX_SIZE=10000;
vector<string> strings;
unsigned int len;

string GetLongestCommonSubstring( string string1, string string2 );
inline void readNumberSubstrings();
inline const string getMaxSubstring();

void readNumberSubstrings()
{
cin >> len;

assert(len > 1 && len <=MAX_STRINGS);

strings.resize(len);

for(register unsigned int i=0; i<len;i++)
strings[i]=string(MAX_SIZE,0);

for(register unsigned int i=0; i<len; i++)
cin>>strings[i];
}

const string getMaxSubstring()
{
string maxSubstring=strings[0];
for(register unsigned int i=1; i < len; i++)
maxSubstring=GetLongestCommonSubstring(maxSubstring, strings[i]);
return maxSubstring;
}

string GetLongestCommonSubstring( string string1, string string2 )
{

const int solution_size = string2.length()+ 1;

int *x=new int[solution_size]();
int *y= new int[solution_size]();

int **previous = &x;
int **current = &y;

int max_length = 0;
int result_index = 0;

int j;
int length;
int M=string2.length() - 1;

for(register int i = string1.length() - 1; i >= 0; i--)
{
for(register int j = M; j >= 0; j--)
{
if(string1[i] != string2[j])
(*current)[j] = 0;
else
{
length = 1 + (*previous)[j + 1];
if (length > max_length)
{
max_length = length;
result_index = i;
}

(*current)[j] = length;
}
}

swap(previous, current);
}
string1[max_length+result_index]='\0';
return &(string1[result_index]);
}

int main()
{
readNumberSubstrings();
cout << getMaxSubstring() << endl;
return 0;
}

Заметка: есть причина, по которой я не написал код, который бы решал эту проблему с помощью суффиксных деревьев (они большие).

0

c++longest-substring optimization

Решение

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

Вы должны использовать суффикс дерева. Эта структура создаст алгоритм, который работает около 1 секунды на 10 строк с 10000 символов.

0

Попробуйте суффикс Arraya, они занимают столько же памяти, сколько и ваши входные строки (в зависимости от кодировки текста), и быстро строятся за линейное время.

http://en.wikipedia.org/wiki/Suffix_array

Вот мой код JavaScript для этого

function LCS(as, bs, A, B) {
var a = 0, b = 0, R = [], max = 1
while (a < A.length && b < B.length) {
var M = cmpAt(as, bs, A[a], B[b])
if (M.size > 0) {
if (M.ab < 0) {
var x = b; while (x < B.length) {
var C = cmpAt(as, bs, A[a], B[x])
if (C.size >= M.size) {  if (C.size >= max) max = C.size, R.push([a, x, C.size]) } else break
x++
}
} else {
var x = a; while (x < A.length) {
var C = cmpAt(as, bs, A[x], B[b])
if (C.size >= M.size) { if (C.size >= max) max = C.size, R.push([x, b, C.size]) } else break
x++
}
}
}
if (M.ab < 0) a++; else b++
}
R = R.filter(function(a){ if (a[2] == max) return true })
return R
}

function cmpAt(a, b, x, y) {
var c = 0
while (true) {
if (x == a.length) {
if (y == b.length) return { size: c, ab: 0 }
return { size: c, ab: -1 }
}
if (y == b.length) return { size: c, ab: 1 }
if (a.charCodeAt(x) != b.charCodeAt(y)) {
var ab = 1;
if (a.charCodeAt(x) < b.charCodeAt(y)) ab = -1
return { size: c, ab: ab }
}
c++, x++, y++
}
}

0

Источник

Accepted Answer

Часто, когда речь заходит об оптимизации, единственным подходящим вариантом может быть другой подход, а не попытка постепенно улучшить текущую реализацию. Вот моя идея:

создать список действительные символы это может появиться в самой длинной общей подстроке. То есть, если символ появляется не во всех строках, он не может быть частью самой длинной общей подстроки.
разделите каждую строку на несколько строк, содержащих только допустимые символы
для каждой такой строки создайте все возможные подстроки и добавьте их в список.
Отфильтруйте (как с символами) все строки, которые не отображаются во всех списках.

Сложность этого, очевидно, во многом зависит от количества недопустимых символов. если это ноль, этот подход не помогает вообще.

Несколько замечаний к вашему коду: не пытайтесь быть слишком умным. Компилятор оптимизирует так много, что вам не нужно ставить register в вашем коде. Во-вторых, ваши строки размещения, а затем перезаписать их (в readNumberSubstrings), это совершенно не нужно. В-третьих, пройдите по ссылке, если можете. В-четвертых, не используйте сырые указатели, особенно если вы никогда delete [] ваш new []д объектов. использование std::vectorВместо этого он ведет себя хорошо с исключениями (с которыми вы можете столкнуться, вы часто используете строки!).

1