가장 긴 공통 부분 시퀀스 번호

Question

두 개의 문자열 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]의 공통 부분 시퀀스의 길이를 나타냅니다. 나는 당신이 trie의 노드에 대한 포인터의 목록을 나타내는 lp [i] [j]를 제안한다. 그 노드에서부터 trie의 루트까지의 경로는 A에 대한 가장 긴 공통 subseq 중 하나를 준다 [ i ... m] 및 B [j..n]. 이 lp를 작성하려면, case 1과 2의 경우 lp [i + 1] [j] 또는 lp [i] [j + 1]의리스트를 모두 Case 4에 복사하고, 3의 경우에는 트리에서 값 A [i] = B [j]를 갖는 트리는 새로운 노드의 아들로서 lp [i + 1] [j + 1]에 의해 지시 된 모든 노드를 설정한다. 이러한 연산은 선형 (또는 집합을 처리하기위한 일부 고급 데이터 구조를 사용하는 경우 더 빠릅니다) 일 수 있습니다. 내가 설명한 것은 실제로 트리/트리가 아닙니다 (노드가 여러 개의 부모를 가질 수 있음).

마지막으로 카운팅을 위해 다음과 같이 몇 가지 추가 처리 - 순회가 좋을 것이라고 생각합니다. count [node] [level] = sum (count [sons (node)] [level-1]) 또는 node가 리프 카운트 [node] [1] = 1이면 count [node] [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]입니다. 내 아이디어가 도움이되기를 바랍니다.