algorithm - 最长公共(public)子序列数

Question

我需要找到两个字符串 A 和 B 之间不同的最长公共(public)子序列的数量。我目前使用的是正常的动态规划方法，然后通过使用回溯数组生成所有不同的子串，然后进行深度优先搜索从起始索引开始。

但是，由于可能的此类答案的数量非常多，我的代码太慢了。有没有办法在不实际生成它们的情况下计算这些不同的最长公共(public)子序列的数量？

到目前为止我的代码:

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

我想你可以使用 rolling hash function就像拉宾卡普的。这样，您就可以计算更长的公共(public)子序列的新哈希值，而无需再次重新生成整个字符串并对其进行哈希处理。

实际上，我认为您可以使用纯 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]。希望我的想法对您有所帮助!