Как получить индексы строковых подпоследовательностей после подсчета количества подпоследовательностей?

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)

Идея состоит в том, чтобы сделать то же самое, что мы используем для вычисления ответа, но вернуть список индексов вместо количества способов.

Я не проверял приведенный выше код, поэтому он может содержать незначительные ошибки, но я думаю, что идея ясна.