सब भन्दा लामो पुनरावृत्ति


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन आर्सेसियम Avalara बाइटडेन्स राजधानी एक फेसबुक MetLife
बाइनरी खोज डायनामिक प्रोग्रामिंग हैश घागो

समस्या "अबदेखि दोहोरिएको उपक्रम" भन्छ कि तपाईंलाई इनपुटको रूपमा एउटा स्ट्रिंग दिइन्छ। सब भन्दा लामो दोहोरिएको अनुउपांक पत्ता लगाउनुहोस्, त्यो उपखण्ड जुन स्ट्रि inमा दुई पटक अवस्थित हुन्छ।

उदाहरणका

सब भन्दा लामो पुनरावृत्ति

aeafbdfdg
3 (afd)

दृष्टिकोण

समस्याले हामीलाई स्ट्रि inमा सब भन्दा लामो दोहोरिएको अनुक्रम फेला पार्न सोध्छ। सम्झनको लागि, एउटा अनुक्रम एक स्ट्रिंग हो जुन तपाईं स्ट्रिंगबाट केही क्यारेक्टरहरू मेटाउनुहुन्छ भने तपाईंले छोडिनुभयो। त्यसोभए, एउटा भोली दृष्टिकोण सबै अनुभागहरूको पुस्ता हुन सक्छ। अनुगामीको उत्पादन पछि, हामी जाँच गर्न थाल्छौं कि कुनै पनि उप-परिच्छेदले हाम्रो आवश्यकता पूरा गर्छ वा गर्दैन। तर एक उपको निर्माणको समय उपभोग प्रक्रिया हो। यसैले हामीले उप-अनुक्रमहरू उत्पादन गर्नुको सट्टा कुनै पनि अन्य दृष्टिकोणको बारेमा सोच्न आवश्यक छ।

हामीले गर्न सक्ने अर्को कुरा भनेको प्रयोग हो गतिशील प्रोग्रामिंग। समस्या यस भन्दा थोरै भिन्नता हो सब भन्दा लामो साझा उप-अनुक्रम। त्यहाँ दुई परिवर्तनहरू छन्। पहिले, दुई स्ट्रिंगको सट्टा, हामी एकल स्ट्रि onमा अपरेटिंग गर्दैछौं। र अर्को कुरा पनि पहिलो तथ्य संग सम्बन्धित छ। हामी एकल स्ट्रि stringमा अपरेटिंग गर्दैछौं र अनुक्रम दोहोरिएको चाहान्छौं। हामीले क्यारेक्टरहरू छनौट गर्न आवश्यक पर्दछ जुन दुबै अनुक्रममा विशेष रूपमा स्वतन्त्र हुन्छ जुन वर्णहरूको सूचकांक भिन्न हुनुपर्दछ। त्यसो भए अझ औपचारिक रूपमा हामी उही फंक्शनलाई कलिंग गर्दछौं सब भन्दा लामो साधारण अनुभाग खोज्नका लागि तर दोस्रो स्ट्रिंग पार गर्नुको सट्टा। हामी पहिलो र दोस्रो आर्गुमेन्टमा समान सर्तहरू सर्तका साथ सर्नेछौं कि उही पात्रहरूको लागि अनुक्रमणिका फरक हुनुपर्दछ।

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), किनभने हामीले २d DP तालिका सिर्जना गर्नुपर्नेछ। यसैले अन्तरिक्ष जटिलता पनि बहुपद हो।