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


Сложный уровень средний
Часто спрашивают в Амазонка Арцезиум Avalara ByteDance Capital One Facebook MetLife
Бинарный поиск Динамическое программирование Hash строка

Задача «Самая длинная повторяющаяся подпоследовательность» заключается в том, что вам на входе дана строка. Найдите самую длинную повторяющуюся подпоследовательность, то есть подпоследовательность, которая существует дважды в строке.

Пример

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

aeafbdfdg
3 (afd)

Подход

Задача просит нас найти самую длинную повторяющуюся подпоследовательность в строке. Напомним, подпоследовательность - это строка, в которой вы останетесь, если удалите некоторые символы из строки. Итак, наивный подход может заключаться в генерации всех подпоследовательностей. После генерации подпоследовательности мы начинаем проверять, удовлетворяет ли какая-либо из подпоследовательностей нашему требованию или нет. Но создание подпоследовательности - это трудоемкий процесс. Таким образом, нам нужно подумать о любом другом подходе вместо генерации подпоследовательностей.

Еще мы можем использовать динамическое программирование. Проблема заключается в небольшом изменении Самая длинная общая подпоследовательность. Есть два изменения. Во-первых, вместо двух строк мы работаем с одной строкой. И другое тоже связано с первым фактом. Поскольку мы работаем с одной строкой и хотим, чтобы подпоследовательность повторялась. Мы требуем выбрать символы, которые исключительно независимы в обеих подпоследовательностях, то есть индекс символов должен быть различным. Таким образом, говоря более формально, мы будем вызывать ту же функцию, чтобы найти самую длинную общую подпоследовательность, но вместо передачи второй строки. Мы передаем одну и ту же строку в качестве первого и второго аргументов с условием, что индексы для одних и тех же символов должны быть разными.

Код C ++ для поиска самой длинной повторяющейся подпоследовательности

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s = "aeafbdfdg";
    int n = s.length();
  int dp[n][n];memset(dp, 0, sizeof dp);
  for (int i=0;i<n;i++){
    for (int j=0;j<n;j++){
      if (s[i]==s[j] && i != j) 
        dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
      else
        dp[i][j] = max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
    }
  }
    cout<<dp[n-1][n-1];
}
3

Код Java для поиска самой длинной повторяющейся подпоследовательности

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    String s = "aeafbdfdg";
      int n = s.length();
    int dp[][] = new int[n+1][n+1]; 
    for (int i=0; i<=n; i++) 
      for (int j=0; j<=n; j++) 
        dp[i][j] = 0;
    for (int i=0;i<n;i++){
      for (int j=0;j<n;j++){
        if (s.charAt(i)==s.charAt(j) && i != j) 
          dp[i][j] = 1 + ((i>0 && j>0) ? dp[i-1][j-1] : 0);
        else
          dp[i][j] = Math.max(((j>0) ? dp[i][j-1] : 0), ((i>0) ? dp[i-1][j] : 0));
      }
    }
    System.out.print(dp[n-1][n-1]);
  }
}
3

Анализ сложности

Сложность времени

О (N ^ 2), потому что этот подход такой же, как и для задачи самой длинной общей подпоследовательности. Таким образом, временная сложность также аналогична этой.

Космическая сложность

О (N ^ 2), потому что нам нужно создать 2D-таблицу DP. Таким образом, сложность пространства также полиномиальна.