6

私の質問は簡単です: 2 つのシーケンス A と B の間で最長の連続したサブシーケンスを見つけるための O(n) アルゴリズムはありますか? 私はそれを検索しましたが、すべての結果は 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 }
4

3 に答える 3

2

はい、線形時間でこれを行うことができます。1 つの方法は、パターンとテキストの両方のサフィックス ツリーを構築し、それらの交差を計算することです。ただし、接尾辞ツリーまたは接尾辞配列を使用せずにこれを行う方法は考えられません。

于 2012-12-25T18:23:03.580 に答える
0

それがあなたが探しているものです：

KMP アルゴリズムの c 実装

基本理論：

  1. C++ を使用して最長共通部分文字列を見つける方法

  2. http://en.wikipedia.org/wiki/Longest_common_substring_problem

于 2012-12-25T18:25:44.123 に答える
0

O(n) アルゴリズムが存在するかどうかはわかりません。これは O(n*n) の動的ソリューションです。役に立つかもしれません。lcs_con[i][j] が、配列 A の要素 A_i と配列 B の要素 B_j で終わる最長の共通連続サブシーケンスを表すとします。次に、以下の式を取得できます。

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;    
}

それが役に立てば幸い！

于 2012-12-26T17:43:32.090 に答える