طولانی ترین پیامد تکرار شده


سطح دشواری متوسط
اغلب در آمازون ارسیسیوم Avalara ByteDance یکی از سرمایه فیس بوک 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

کد جاوا برای یافتن طولانی ترین پیامد تکرار شده

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) ، زیرا ما باید یک جدول DD 2D ایجاد کنیم. بنابراین پیچیدگی فضا نیز چند جمله ای است.