გრძელი განმეორებითი შედეგი


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon არსიუმი ავალარა ByteDance Capital One Facebook MetLife
ორობითი ძებნა დინამიური პროგრამირება Hash სიმებიანი

პრობლემა "გრძელი განმეორებითი შედეგი" აცხადებს, რომ შენთვის მოცემულია სტრიქონი. გაარკვიეთ გრძელი განმეორებითი თანმიმდევრობა, ეს არის თანმიმდევრობა, რომელიც სტრიქონში ორჯერ არსებობს.

მაგალითი

გრძელი განმეორებითი შედეგი

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 ცხრილი. ამრიგად, სივრცის სირთულე ასევე მრავალწევრია.