Ең ұзақ қайталанатын кейінгі нәтиже  


Күрделілік дәрежесі орта
Жиі кіреді Amazon Арцезий Авалара ByteDance Capital One Facebook MetLife
Екілік іздеу Динамикалық бағдарламалау Hash String

«Ең ұзақ қайталанатын кейінгі іздеу» проблемасында сізге кіріс ретінде жол берілгендігі айтылған. Ең ұзақ қайталанатын тізбекті анықтаңыз, бұл жолда екі рет болатын тізбекті білдіреді.

мысал  

Ең ұзақ қайталанатын кейінгі нәтижетүйреуіш

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 кестесін жасауымыз керек. Сонымен кеңістіктің күрделілігі де көпмүшелік болып табылады.