最も長い共通部分列の数

Question

2つの文字列AとBの間で、最も長い共通部分配列の個数を見つける必要があります。現在、通常の動的プログラミング手法を使用しています。そして、バックトラック配列を使用して、開始インデックスから深さの最初の検索を行います。

しかし、そのような可能性のある回答の数が非常に多いので、私のコードは遅すぎます。そのような最も長い共通サブシーケンスの数を実際に生成せずに数える方法はありますか？

これまでの私のコード：

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Arrays; 
import java.util.HashSet; 
import java.util.Iterator; 
import java.util.Stack; 

class Node 
{ 
String res = ""; 
int i; 
int j; 

public Node(int _i, int _j, String s) 
{ 
    i = _i; 
    j = _j; 
    res = s; 
} 
} 

public class LCSRevisited 
{ 
static String a; 
static String b; 
static int m,n; 
static int[][] memo; 
static int[][] bt; // 1 means [i+1][j], 2 means [i][j+1], 3 means [i+1][j+1] 
// 4 - means both 

static HashSet <String> filter; 

static void printAllStrings() 
{ 
    Iterator i = filter.iterator(); 

    while(i.hasNext()) 
    { 
     System.out.println(i.next()); 
    } 
} 

static void printSol() 
{ 
    System.out.print(memo[ 0 ][ 0 ]); 

    // check how many UNIQUE such strings exist 

    filter = new HashSet(); 
    Stack<Node> s = new Stack(); 
    Node start = new Node(0, 0, ""); 
    s.push(start); 
    Node curr; 
    String res; 

    // use backtrack array to do a DFS 

    while(!s.isEmpty()) 
    { 
     curr = s.pop(); 
     res = curr.res; 

     if((curr.i>=m) || (curr.j >=n)) 
     { 
      filter.add(curr.res); 
      continue; 
     } 

     // check backtrack value 
     int i = curr.i; 
     int j = curr.j; 
     int back = bt[ i ][ j]; 

     if(back == 1) 
     { 
      s.push(new Node(i+1, j, res)); 
     } 
     if(back == 2) 
     { 
      s.push(new Node(i, j+1, res)); 
     } 
     if(back == 3) 
     { 
      s.push(new Node(i+1, j+1, res+a.charAt(i))); 
     } 
     if(back == 4) 
     { 
      s.push(new Node(i, j+1, res)); 
      s.push(new Node(i+1, j, res)); 
     } 
    } 
    //printAllStrings(); 
    System.out.println(" " + filter.size()); 
} 

static void solve() 
{ 
    // fill base cases 
    m = a.length(); 
    n = b.length(); 
    memo = new int[ m+1 ][ n+1 ]; 
    Arrays.fill(memo[m], 0); 

    bt = new int[ m+1 ][ n+1 ]; 

    for(int i=0; i<m; i++) 
    { 
     memo[ i ][ n ] = 0;  
    } 

    // Now compute memo values 
    for(int i=m-1; i>=0; i--) 
    { 
     for(int j=n-1; j>=0; j--) 
     { 
      if(a.charAt(i) == b.charAt(j)) 
      { 
       memo[ i ][ j ] = 1 + memo[ i+1 ][ j+1 ]; 
       bt[ i ][ j ] = 3; 
      } 
      else 
      { 
       int r1 = memo[ i+1 ][ j ]; 
       int r2 = memo[ i ][ j+1 ]; 

       if(r1==r2) 
       { 
        memo[ i ][ j ] = r1; 
        bt[ i ][ j ] = 4; 
       } 
       else if(r1 > r2) 
       { 
        memo[ i ][ j ] = r1; 
        bt[ i ][ j ] = 1; 
       } 
       else 
       { 
        memo[ i ][ j ] = r2; 
        bt[ i ][ j ] = 2; 
       } 
      } 
     } 
    } 

    printSol(); 
} 

public static void main(String[] args) throws IOException 
{ 
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 

int T= Integer.parseInt(br.readLine()); 

while(T--> 0) 
{ 
    a = br.readLine(); 
    b = br.readLine(); 

    if(T>=1) 
    br.readLine(); 

    solve(); 
    // printArr(bt); 
} 
} 
} 

Answer 1

はたぶんトライの種類を使用すると、あなたは長さを計算しながら、あなたは実際のシーケンスを生成することができ、および計算後のトライで横断して合計数（線形時間）。

ここで、memo [i] [j]はA [i ... m]とB [j..n]の共通部分列の長さを表します。私はあなたがまた、そのノードからトライのルートへのパスがあなたに最も長い共通のsubseqの1つを与えるように、トライのノードへのポインタのリストを表すlp [i] [j] i ... m]およびB [j..n]を含む。このlpを構築するには、ケース1とケース2の場合、lp [i + 1] [j]またはlp [i] [j + 1]からリストをコピーします。ツリー内の値A [i] = B [j]を有するツリーは、新しいノードの子としてlp [i + 1] [j + 1]によって指し示されるすべてのノードを設定する。これらの操作は線形（または、おそらくセットを扱うためのいくつかの高度なデータ構造でより速い）でしょう。私が記述したことは、実際にはトライ/ツリー（ノードは複数の親を持つことができる）ではないことに注意してください。

最終的には、トラバーサルが良いと思う、いくつかの追加の処理 - カウントを伝播すると思う：count [node] [level] = sum（count [sons（node）] [level-1]）ノードがリーフ・カウントであれば[ノード] [1] = 1、カウント[ノード] [l！= 1] = 0。あなたの答えは、 "最長"の制約（\ sum_x {count [x] [l_max]）を満たす "ルート"ノード（in-degree 0）の総数です。

私は自分の解決策を100％確信しているわけではありませんが、問題に対する改善された回答が得られる可能性があります。

Answer 2

私はあなたがRabin Karp'sのようなrolling hash functionを使用できると思っています。そうすれば、文字列全体を再生成してハッシュすることなく、より長い共通部分列の新しいハッシュ値を計算することができます。

実際、私は純粋なDPを使って答えを見つけることができると思います。 LCS用のDPテーブルの値を既に計算したとします（コード内にmemo[][]と思います）。次に、このような異なるLCSインスタンスの数を計算することができます

for j ← 0 to n do 
    for i ← 0 to m do 
     if i = 0 or j = 0 then 
      D[i, j] ← 1 
     else 
      D[i, j] ← 0 
      if ai = bj then 
       D[i, j] ← D[i − 1, j − 1] 
      else if L[i − 1, j] = L[i, j] then 
       D[i, j] ← D[i, j] + D[i − 1, j] 
      endif 
      if L[i, j − 1] = L[i, j] then 
       D[i, j] ← D[i, j] + D[i, j − 1] 
      endif 
      if L[i − 1, j − 1] = L[i, j] then 
       D[i, j] ← D[i, j] − D[i − 1, j − 1] 
      endif 
     end if 
    endfor 
endfor 

あなたの答えはD [n、m]です。 私のアイデアが助けてくれることを願っています！