Самая длинная общая непрерывная подпоследовательность — алгоритм

Question

Самая длинная общая непрерывная подпоследовательность — алгоритм

Мой вопрос прост: существует ли алгоритм O (n) для нахождения самой длинной непрерывной подпоследовательности между двумя последовательностями A и B? Я искал это, но все результаты были о проблеме LCS, которая не то, что я ищу.

Замечания: Если вы готовы предоставить какой-либо пример кода, вы можете сделать это, но, пожалуйста, если вы можете, на C или C ++.

Редактировать: Вот пример:

A: { a, b, a, b, b, b, a }
B: { a, d, b, b, b, c, n }
longest common contiguous subsequence: { b, b, b }

3

algorithm c++sequences

Решение

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

это то, что вы ищете:

Алгоритм КМП c реализация

основная теория:

0

Я не уверен, существует ли алгоритм O (n). Вот O (n * n) динамическое решение, может быть, оно полезно для вас. Пусть lcs_con [i] [j] представляет самую длинную общую смежную подпоследовательность, которая заканчивается элементом A_i из массива A и B_j из массива B. Тогда мы можем получить уравнения ниже:

lcs_con[i][j]=0 if i==0 or j==0
lcs_con[i][j]=0 if A_i != B_j
lcs_con[i][j]=lcs_con[i-1][j-1] if A_i==B_j

мы можем записать максимум lcs_con [i] [j] и конечный индекс во время вычисления, чтобы получить самую длинную общую непрерывную подпоследовательность. Код ниже:

#include<iostream>

using namespace std;int main()
{
char A[7]={'a','b','a','b','b','b','a'};
char B[7]={'a','d','b','b','b','c','n'};

int lcs_con[8][8];
memset(lcs_con,0,8*8*sizeof(int));

int result=-1;
int x=-1;
int y=-1;

for(int i=1;i<=7;++i)
for(int j=1;j<=7;++j)
{
if(A[i-1]==B[j-1])lcs_con[i][j]=lcs_con[i-1][j-1]+1;
else lcs_con[i][j]=0;

if(lcs_con[i][j]>result)
{
result=lcs_con[i][j];
x=i;
y=j;
}
}

if(result==-1)cout<<"There are no common contiguous subsequence";
else
{
cout<<"The longest common contiguous subsequence is:"<<endl;
for(int i=x-result;i<x;i++)cout<<A[i];
cout<<endl;
}

getchar();
getchar();

return 0;
}

Надеюсь, поможет!

0

Источник

Accepted Answer

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

1