Ամենաերկար կրկնվող հետևանքը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Արսիսիում Ավալարա ByteDance Capital One facebook MetLife
Երկուական որոնում Դինամիկ ծրագրավորում Խանգարել 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N ^ 2), քանի որ այս մոտեցումը նույնն է, ինչ «Ամենաերկար ընդհանուր հետևանքի» խնդիրը: Այսպիսով, ժամանակի բարդությունը նույնպես նման է դրան:

Տիեզերական բարդություն

O (N ^ 2), քանի որ մենք պետք է ստեղծենք 2D DP աղյուսակ: Այսպիսով, տիեզերական բարդությունը նույնպես բազմանդամ է: