가장 긴 반복 하위 시퀀스


난이도 중급
자주 묻는 질문 아마존 아르 세슘 아 발라 라 ByteDance 자본 하나 페이스북 서비스 메트 라이프
이진 검색 동적 프로그래밍 해시

"Longest Repeated Subsequence"문제는 문자열이 입력으로 제공된다는 것을 나타냅니다. 가장 긴 반복 하위 시퀀스, 즉 문자열에 두 번 존재하는 하위 시퀀스를 찾습니다.

가장 긴 반복 하위 시퀀스

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

복잡성 분석

시간 복잡성

O (N ^ 2), 이 접근법은 Longest Common Subsequence 문제의 접근법과 동일하기 때문입니다. 따라서 시간 복잡성도 그것과 유사합니다.

공간 복잡성

O (N ^ 2), 2D DP 테이블을 만들어야하기 때문입니다. 따라서 공간 복잡성도 다항식입니다.