Тӯлонитарин пайдоиши такрорӣ


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Артезий Авалара 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N ^ 2), зеро ин равиш бо усули мушкилоти пайдарпайи дарозтарин аст. Ҳамин тавр мураккабии вақт низ ба он монанд аст.

Мураккабии фазо

O (N ^ 2), зеро мо бояд ҷадвали DP 2D созем. Ҳамин тариқ, мураккабии фазо низ полиномия аст.