Ich muss die Anzahl der unterschiedlichen längsten gemeinsamen Teilfolgen zwischen zwei Zeichenfolgen A und B finden. Ich verwende derzeit den normalen dynamischen Programmierungsansatz und generiere dann alle unterschiedlichen Teilfolgen, indem ich ein Backtrack-Array verwende und dann eine Tiefensuche ab dem Startindex durchführe.
Da jedoch die Anzahl möglicher Antworten sehr hoch ist, ist mein Code zu langsam. Gibt es eine Möglichkeit, die Anzahl solcher unterschiedlichen längsten gemeinsamen Teilfolgen zu zählen, ohne sie tatsächlich zu generieren?
Bisheriger Code:
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 bedeutet [i+1][j], 2 bedeutet [i][j+1], 3 bedeutet [i+1][j+1]
// 4 - bedeutet beides
static HashSet 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 ]);
// Überprüfen, wie viele EINZIGARTIGE solche Zeichenfolgen existieren
filter = new HashSet();
Stack s = new Stack();
Node start = new Node( 0, 0, "" );
s.push( start );
Node curr;
String res;
// Verwenden des Backtrack-Arrays, um eine Tiefensuche durchzuführen
while( !s.isEmpty() )
{
curr = s.pop();
res = curr.res;
if( ( curr.i>=m) || ( curr.j >=n ) )
{
filter.add( curr.res);
continue;
}
// Überprüfen des Backtrack-Wertes
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()
{
// Basissituationen ausfüllen
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=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 );
}
}
}
