দীর্ঘতম পুনরাবৃত্ত উপসর্গ


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আরেসিয়াম Avalara ByteDance ক্যাপিটাল ওয়ান ফেসবুক দেখা জীবন
বাইনারি অনুসন্ধান ডায়নামিক প্রোগ্রামিং কাটা স্ট্রিং

"দীর্ঘতম পুনরাবৃত্ত উপসর্গ" সমস্যাটি বলে যে আপনাকে একটি ইনপুট হিসাবে একটি স্ট্রিং দেওয়া হয়। দীর্ঘতম পুনরাবৃত্ত অনুচ্ছেদটি সন্ধান করুন, এটিই পরেরটি যা স্ট্রিংয়ে দু'বার উপস্থিত থাকে।

উদাহরণ

দীর্ঘতম পুনরাবৃত্ত উপসর্গ

aeafbdfdg
3 (afd)

অভিগমন

সমস্যাটি স্ট্রিংয়ের দীর্ঘতম পুনরাবৃত্ত অনুচ্ছেদটি জানতে আমাদের জিজ্ঞাসা করে। মনে রাখার জন্য, একটি অনুচ্ছেদটি একটি স্ট্রিং যা আপনি স্ট্রিং থেকে কিছু অক্ষর মুছলে আপনি রেখে যান। সুতরাং, একটি নির্বোধ দৃষ্টিভঙ্গি সমস্ত অনুচ্ছেদের প্রজন্ম হতে পারে। উপসর্গের প্রজন্মের পরে, আমরা পরবর্তী অংশগুলির কোনওটি আমাদের প্রয়োজনীয়তা পূরণ করে কিনা তা পরীক্ষা করে শুরু করি। তবে একটি উপসর্গের প্রজন্ম সময় সাপেক্ষ প্রক্রিয়া। সুতরাং আমাদের উপসর্গগুলি তৈরির পরিবর্তে অন্য কোনও পদ্ধতির কথা ভাবা দরকার।

অন্য যে জিনিসটি আমরা করতে পারি তা হ'ল ব্যবহার গতিশীল প্রোগ্রামিং। সমস্যাটি এর চেয়ে কিছুটা ভিন্নতা দীর্ঘতম কমন সাবসেক্সেন্স। দুটি পরিবর্তন আছে। প্রথমত, দুটি স্ট্রিংয়ের পরিবর্তে, আমরা একটি স্ট্রিংয়ে অপারেটিং করছি। এবং অন্য জিনিসটিও প্রথম সত্যের সাথে সম্পর্কিত। যেহেতু আমরা একটি একক স্ট্রিংয়ে অপারেটিং করছি এবং চান যে পরবর্তীটি পুনরাবৃত্তি করা উচিত। আমাদের দুটি অক্ষরের মধ্যে স্বতন্ত্রভাবে স্বতন্ত্র অক্ষরগুলি নির্বাচন করতে হবে যা অক্ষরের সূচক আলাদা হতে হবে। তাই আরও আনুষ্ঠানিকভাবে বলতে গেলে আমরা একই ফাংশনটিকে দীর্ঘতম সাধারণ অনুচ্ছেদটি সন্ধান করতে বলব তবে দ্বিতীয় স্ট্রিংটি পাস করার পরিবর্তে। আমরা প্রথম এবং দ্বিতীয় যুক্তির মতো একই স্ট্রিংটি শর্ত দিয়ে পাস করি যে একই অক্ষরের সূচকটি আলাদা হওয়া উচিত।

দীর্ঘতম পুনরাবৃত্ত সাবসেক্সেন্স সন্ধান করতে সি ++ কোড

#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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 2), কারণ এই পদ্ধতিটি দীর্ঘতম কমন সাবসেক্সেন্স সমস্যার মতো। সুতরাং সময়ের জটিলতাও এর সাথে সমান।

স্পেস জটিলতা ity

ও (এন ^ 2), কারণ আমাদের একটি 2D ডিপি টেবিল তৈরি করতে হবে। সুতরাং স্থান জটিলতাও বহুপদী।