Количество самых длинных общих подпоследовательностей

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

Я думаю, вы можете использовать прокручивающую хеш-функцию , как у Рабина Карпа. Таким образом, вы можете вычислить новые значения хеш-функции более длинных общих подпоследовательностей без необходимости повторной генерации всей строки и ее хеширования.

На самом деле, я думаю, что вы можете использовать чистый DP, чтобы найти свой ответ. Предположим, вы уже вычислили значения таблицы DP для LCS (я думаю, что в вашем коде 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]. Надеюсь, что мои идеи помогли!

Answer 2

Возможно, использование некоторого вида дерева может помочь вам сгенерировать фактические последовательности, пока вы вычисляете длину, а после вычисляете общее число с помощью обхода по дереву (линейное время).

Теперь memo [i] [j] представляет длину общей подпоследовательности A [i ... m] и B [j..n]. Я предлагаю, чтобы у вас также был lp [i] [j], представляющий список указателей, каждый на узел в дереве, так что путь от этого узла до корня дерева дает вам один из самых длинных общих подпоследовательностей для A [ я ... м] и B [j..n]. Чтобы построить этот lp, для случаев 1 и 2 вы просто копируете списки из lp [i + 1] [j] или lp [i] [j + 1], оба для случая 4, а для 3 вы добавляете новый узел в дерево со значением A [i] = B [j] и в дереве задают все узлы, указанные lp [i + 1] [j + 1], как сыновей нового узла. Эти операции будут линейными (или, возможно, даже быстрее с некоторыми продвинутыми структурами данных для работы с наборами). Обратите внимание, что то, что я описал, на самом деле не дерево / дерево (у узла может быть несколько родителей).

Наконец, для подсчета, я думаю, что обход был бы хорошим, с некоторой дополнительной обработкой - распространением подсчетов: count [узел] [уровень] = сумма (количество [сыновья (узел)] [уровень-1]) или , если узел - это число листьев [узел] [1] = 1, количество [узел] [l! = 1] = 0. И ваш ответ будет суммированием для тех «корневых» узлов (в градусах 0), которые удовлетворяют «самому длинному» ограничению (\ sum_x {count [x] [l_max]}).

Я не уверен на 100% в своем решении, но это может быть хорошим началом для более качественного ответа на вашу проблему.