Самая длинная общая палиндромная подпоследовательность

Question

Есть ли эффективный алгоритм, который считает длину самой длинной общей палиндромной подпоследовательности двух заданных строк?

например:

Строка 1. afbcdfca

Строка 2. bcadfcgyfka

LCPS равен 5, а строка LCPS равна afcfa,

Answer 1

Да.

Просто используйте алгоритм для LCS для более чем двух последовательностей.

Если я не ошибаюсь, то

 LCS( afbcdfca, acfdcbfa, bcadfcgyfka, akfygcfdacb) = afcfa

Это зависит от вас, чтобы выяснить строки № 2 и № 4.

Обновление: нет, вот контрпример: LCS( aba, aba, bab, bab) = ab, ba. LCS не гарантирует, что подпоследовательность будет палиндромом, вам, вероятно, нужно добавить это ограничение. В любом случае, рекуррентное уравнение для LCS является хорошей отправной точкой.

Если вы реализуете LCS в стиле генератора, чтобы он генерировал все LCS длины n, затем n-1, n-2 и т. Д., То вы должны быть в состоянии достаточно эффективно вычислять самый длинный общий элемент в LCS-gen(string1, обратная строка1), LCS-gen(строка2, обратная строка2). Но я еще не проверял, существует ли высокоэффективный LCS-gen.

Answer 2

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

1) Оптимальная субструктура: пусть X[0..n-1] быть входной последовательностью длины n и L(0, n-1) длина самой длинной палиндромной подпоследовательности X[0..n-1].

Если последний и первый символы X совпадают, то L(0, n-1) = L(1, n-2) + 2, подожди почему, что если 2-ой и 2-ой и последний символы не совпадают, последние и первые одинаковые символы будут бесполезны. Нет, эта "подпоследовательность" не должна быть непрерывной.

/* Driver program to test above functions */
int main()
{
    char seq[] = "panamamanap";
    int n = strlen(seq);
    printf ("The lnegth of the LPS is %d", lps(seq, 0, n-1));
    getchar();
    return 0;
}

int lps(char *seq, int i, int j)
{   
    // Base Case 1: If there is only 1 character   
    if (i == j)     
        return 1;    

    // Base Case 2: If there are only 2 characters and both are same   
    if (seq[i] == seq[j] && i + 1 == j)     
        return 2;    

    // If the first and last characters match   
    if (seq[i] == seq[j])      
        return lps (seq, i+1, j-1) + 2;    

    // If the first and last characters do not match   
    else return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}

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

               L(0, 5)
             /        \ 
            /          \  
        L(1,5)          L(0,4)
       /    \            /    \
      /      \          /      \
  L(2,5)    L(1,4)  L(1,4)  L(0,3)

В приведенном выше дереве частичной рекурсии L(1, 4) решается дважды. Если мы нарисуем полное дерево рекурсии, то увидим, что есть много подзадач, которые решаются снова и снова. Как и другие типичные проблемы динамического программирования (DP), повторных вычислений тех же подзадач можно избежать, создав временный массив L[][] снизу вверх.

// Возвращает длину самой длинной палиндромной подпоследовательности в seq

int lps(char *str)
{
   int n = strlen(str);
   int i, j, cl;
   int L[n][n];  // Create a table to store results of subproblems


   // Strings of length 1 are palindrome of length 1
   for (i = 0; i < n; i++)
      L[i][i] = 1;

    for (cl=2; cl<=n; cl++)                              //again this is the length of chain we are considering
    {
        for (i=0; i<n-cl+1; i++)                         //start at i
        {
            j = i+cl-1;                                  //end at j
            if (str[i] == str[j] && cl == 2)             //if only 2 characters and they are the same then set L[i][j] = 2
               L[i][j] = 2;
            else if (str[i] == str[j])                   //if greater than length 2 and first and last characters match, add 2 to the calculated value of the center stripped of both ends
               L[i][j] = L[i+1][j-1] + 2;
            else
               L[i][j] = max(L[i][j-1], L[i+1][j]);      //if not match, then take max of 2 possibilities
        }
    }

    return L[0][n-1];
}

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

Answer 3

Это так же, как эта проблема: http://code.google.com/codejam/contest/1781488/dashboard

http://code.google.com/codejam/contest/1781488/dashboard

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

При динамическом программировании существуют только состояния len(s1)*len(s1)/2, поэтому возможен порядок (N^2).

Идея в том, чтобы либо взять символ из s1, либо не брать его. Если вы снимаете символ с s1, вы должны снять его спереди и сзади (как s1, так и s2). Если вы не берете его, вы продвигаетесь вперед 1. (это означает, что состояние s2 синхронизируется с состоянием s1, потому что вы всегда жадно воспринимаете внешнюю сторону обоих - так что вы беспокоитесь только о том, сколько состояний может иметь s1).

Этот код дает вам большую часть пути туда. cd1 (char dict 1) помогает вам найти следующий символ в s1, равный тому символу, на котором вы находитесь (и вперед, и назад).

В рекурсивном методе solve () вам нужно решить, какими должны быть start1, end1.. и т. Д. Добавляйте 2 к общему числу каждый раз, когда вы берете символ (если только start1 == end1 - затем добавьте 1)

s1 = "afbcdfca"
s2 = "bcadfcgyfka"

def cd(s):
    """returns dictionary d where d[i] = j where j is the next occurrence of character i"""
    char_dict = {}
    last_pos = {}
    for i, char in enumerate(s):
        if char in char_dict:
            _, forward, backward = char_dict[char]
            pos = last_pos[char]
            forward[pos] = i
            backward[i] = pos
            last_pos[char] = i
        else:
            first, forward, backward = i, {}, {}
            char_dict[char] = (first, forward, backward)
            last_pos[char] = i
    return char_dict

print cd(s1)
"""{'a': ({0: 7}, {7: 0}), 'c': ({3: 6}, {6: 3}), 'b': ({}, {}), 'd': ({}, {}), 'f': ({1: 5}, {5: 1})}"""

cd1, cd2 = cd(s1), cd(s2)

cache = {}
def solve(start1, end1, start2, end2):
    state = (start1, end1)
    answer = cache.get(state, None)
    if answer:
        return answer

    if start1 < end1:
        return 0
    c1s, c1e = s1[start1], s1[end1]
    c2s, c2e = s2[start2], s2[end2]

    #if any of c1s, c1e, c2s, c2e are equal and you don't take, you must
    #skip over those characters too:
    dont_take_end1 = solve(start1, end1 - 1, start2, end2)

    do_take_end1 = 2
    if do_take_end1:
        end1_char = s1[end1]
        #start1 = next character along from start1 that equals end1_char
        #end1 = next char before end1 that equals end1_char
        #end2 = next char before end2 that..
        #start2 = next char after .. that ..
        do_take_end1 += solve(start1, end1, start2, end2)


    answer = cache[state] = max(dont_take_end1, do_take_end1)
    return answer

print solve(0, len(s1), 0, len(s2))