Алгоритм скорейшей общей подпоследовательности (LCS)

Question

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

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

Answer 1

Это почти то же самое, что и DP минус часть memoization.

LCS(s1, s2, i, j): 
    if(i == -1 || j == -1) 
     return 0 
    if(s1[i] == s2[j]) 
     return 1 + LCS(s1, s2, i-1, j-1) 
    return max(LCS(s1, s2, i-1, j), LCS(s1, s2, i, j-1)) 

Идея заключается в том, если у нас есть две строки s1 и s2, где s1 заканчивается я и s2 заканчивается у, то ЛВП:

• если либо строка пуста, то длинный общий подпоследовательность равна 0.
• Если последний символ (индекс i) строки 1 совпадает с последним в строке 2 (индекс j), тогда ответ равен 1 плюс LCS s1 и s2, заканчивающийся на i-1 и j-1 соответственно. Потому что очевидно, что эти два индекса вносят вклад в LCS, поэтому их оптимально подсчитывать.
• Если последние символы не совпадают, мы пытаемся удалить один из символов. Поэтому мы пытаемся найти LCS между s1 (заканчивающийся на i-1) и s2 (заканчивающийся на j) и LCS между s1 (заканчивающийся на i) и s2 (заканчивающийся на j-1), а затем взять максимум обоих.

Временная сложность, очевидно, экспоненциальная.

Answer 2

Мне нравится @ turingcomplete ответ, но это не очень грубая сила, поскольку на самом деле он не перечисляет все варианты решений. Например, если строки являются «ABCDE» и «XBCDY», рекурсивный подход не будет проверять «ABC» по сравнению с «XBC», потому что тест «A» по сравнению с «X» уже провалился. Это вопрос мнения, хотите ли вы считать это уникальным кандидатом. Фактически, вы можете утверждать, что «ABC» по сравнению с «ABCDY» также является допустимым кандидатом и сразу же выходит из строя из-за разницы в длине. Вы можете добавить отдельные LA и LB к приведенному ниже коду, чтобы в полной мере перечислять этих кандидатов.

for L = min(A.length, B.length) to 1 
{ 
    for iA = 0 to A.length - L - 1 
    { 
     for iB = 0 to B.length - L - 1 
     { 
      for i = 0 to L - 1 
      { 
       if(A[iA] != B[iB]) 
       { 
        match failed; 
       } 
      } 
      if match didn't fail, then 
      A[iA..iA+L] and B[iB..iB+L] are a maximal common substring 
     } 
    } 
} 
no common substring