Најдолга повторена последица


Ниво на тешкотија Медиум
Често прашувано во Амазон Арцесиум Avalara ByteDance капитал Еден 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

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

Временска комплексност

О (N ^ 2), бидејќи овој пристап е ист со оној на проблемот со најдолгата заедничка последица. Така, временската сложеност е исто така слична на таа.

Комплексноста на просторот

О (N ^ 2), затоа што треба да создадеме 2D DP табела. Така, вселенската комплексност е исто така полиномна.