如何在计算子序列数后获取字符串子序列索引？

Question

给出以下算法来计算一个字符串作为另一个字符串的子序列出现的次数并给出最终数字，我将如何实现一个例程来给我字符串的索引。例如，如果有 4 个字符串作为另一个字符串的子序列出现，我将如何找到每个字符串的索引？ [1][4][9] 第一个字符串从我自己解决问题的尝试来看，在 dp 查找 table 上有一个模式，我在视觉上看到但很难在代码中实现，我将如何添加一个回溯，它会给我每个字符串子序列的索引，因为它出现。在示例中，我知道字符串将作为子序列出现的次数，但我想知道每个子序列出现的字符串索引，如前所述，当我查看查找 table 值时，我可以直观地确定这一点，但很难编码吗？我知道解决方案在于回溯表格查找容器

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)

我们的想法是做与我们用来计算答案完全相同的事情，但是 return 索引列表而不是方法数。

我没有测试过上面的代码，所以它可能包含一些小错误，但我认为思路很清楚。

如何在计算子序列数后获取字符串子序列索引？

How do I obtain string subsequence indices after counting number of subsequences?

algorithm

dynamic-programming

subsequence