サブシーケンス数を数えた後、どのように文字列サブシーケンスインデックスを取得しますか？

Question

文字列が別の文字列のサブシーケンスとして表示される回数をカウントし、最後の数値を与えるアルゴリズムが与えられた場合、どのように文字列のインデックスを与えるルーチンを実装するのですか？例えば、4つの文字列が別の文字列のサブシーケンスとして現れている場合、どのように各文字列のインデックスを見つけることができますか？ [1] [4] [9]最初の文字列 問題を解決するための私自身の試みから、視覚的には見えますがコードで実装するのに苦労するdp参照テーブルのパターンがあります。表示される各文字列の部分列のインデックスを私に与えてください。この例では、文字列がサブシーケンスとして表示される回数を知っていますが、各サブシーケンスの外観の文字列インデックスを知りたいのですが、ルックアップテーブルの値を見ると視覚的に判断できますが、私は解決策は、表形式のルックアップコンテナをバックトラック

int count(string a, string b) 
{ 
    int m = a.length(); 
    int n = b.length(); 


    int lookup[m + 1][n + 1] = { { 0 } }; 

    // If first string is empty 
    for (int i = 0; i <= n; ++i) 
     lookup[0][i] = 0; 

    // If second string is empty 
    for (int i = 0; i <= m; ++i) 
     lookup[i][0] = 1; 

    // Fill lookup[][] in bottom up 
    for (int i = 1; i <= m; i++) 
    { 
     for (int j = 1; j <= n; j++) 
     { 
      // we have two options 
      // 
      // 1. consider last characters of both strings 
      // in solution 
      // 2. ignore last character of first string 
      if (a[i - 1] == b[j - 1]) 
       lookup[i][j] = lookup[i - 1][j - 1] + 
           lookup[i - 1][j]; 

      else 
       // If last character are different, ignore 
       // last character of first string 
       lookup[i][j] = lookup[i - 1][j]; 
     } 
    } 

    return lookup[m][n]; 
} 
int main(void){ 
string a = "ccaccbbbaccccca"; 
string b = "abc"; 

cout << count(a, b); 

return 0; 

} 

Answer 1

にあなたは（基本的に、あなただけの別の方向に同じことをやっているでしょう）を再帰的にそれを行うことができある知っている：

def gen(i, j): 
    // If there's no match, we're done 
    if lookup[i][j] == 0: 
     return [] 
    // If one of the indices is 0, the answer is an empty list 
    // which means an empty sequence 
    if i == 0 or j == 0: 
     return [[]] 
    // Otherwise, we just do all transitions backwards 
    // combine the results 
    res = [] 
    if a[i - 1] == b[j - 1]: 
     res = gen(i - 1, j - 1) 
     for elem in res: 
       elem.append(a[i - 1]) 
    return res + gen(i - 1, j) 

アイデアがあります答えを計算するのに使うのとまったく同じことをするだけでなく、多くの方法の代わりにインデックスのリストを返すことです。

私は上記のコードをテストしていないため、小さなバグが含まれている可能性がありますが、そのアイデアははっきりしていると思います。