Самая доўгая паўторная паслядоўнасць


Узровень складанасці серада
Часта пытаюцца ў амазонка Арцэзіум Avalara ByteDance Capital One facebook MetLife
Двайковы пошук Дынамічнае праграмаванне гашыш Радок

Праблема "Самая доўгая паўторная паслядоўнасць" абвяшчае, што вам даецца радок у якасці ўваходных дадзеных. Даведайцеся самую доўгую паўторную паслядоўнасць, гэта значыць падпасляднасць, якая існуе двойчы ў радку.

Прыклад

Самая доўгая паўторная паслядоўнасць

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), таму што гэты падыход такі ж, як і падыход да самай доўгай агульнай праблемы наступстваў. Такім чынам, часавая складанасць таксама падобная на такую.

Касмічная складанасць

O (N ^ 2), таму што мы павінны стварыць табліцу 2D DP. Такім чынам, касмічная складанасць таксама мнагачленная.