ਲੰਬੇ ਸਮੇਂ ਤੋਂ ਦੁਹਰਾਇਆ ਜਾਣ ਵਾਲਾ ਸਬਕ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਆਰਸੀਸੀਅਮ ਅਵਲਾਰਾ ਬਾਈਟਡੈਂਸ ਕੈਪੀਟਲ ਇਕ ਫੇਸਬੁੱਕ ਮੈਟਲਾਈਫ
ਬਾਈਨਰੀ ਖੋਜ ਡਾਇਨਾਮਿਕ ਪ੍ਰੋਗਰਾਮਿੰਗ ਹੈਸ਼ ਸਤਰ

ਸਮੱਸਿਆ “ਲੰਬੇ ਸਮੇਂ ਤੋਂ ਦੁਹਰਾਉਣ ਵਾਲਾ ਸਬਸਿਉਂਸ” ਕਹਿੰਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੰਪੁੱਟ ਦੇ ਤੌਰ ਤੇ ਇੱਕ ਸਤਰ ਦਿੱਤੀ ਜਾਂਦੀ ਹੈ. ਸਭ ਤੋਂ ਲੰਬੇ ਦੁਹਰਾਏ ਉਪਗ੍ਰਹਿ ਦਾ ਪਤਾ ਲਗਾਓ, ਇਹ ਉਹ ਸਬਕੁਐਂਸ ਹੈ ਜੋ ਕਿ ਸਤਰ ਵਿੱਚ ਦੋ ਵਾਰ ਮੌਜੂਦ ਹੈ.

ਉਦਾਹਰਨ

ਲੰਬੇ ਸਮੇਂ ਤੋਂ ਦੁਹਰਾਇਆ ਜਾਣ ਵਾਲਾ ਸਬਕ

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), ਕਿਉਂਕਿ ਇਹ ਪਹੁੰਚ ਉਨੀ ਹੀ ਆਮ ਹੈ ਜੋ ਸਭ ਤੋਂ ਲੰਬੇ ਸਮੇਂ ਦੀ ਆਮ ਸਬਸਕੈਂਸ ਦੀ ਸਮੱਸਿਆ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਸਮੇਂ ਦੀ ਗੁੰਝਲਦਾਰਤਾ ਵੀ ਇਸ ਦੇ ਸਮਾਨ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ ^ 2), ਕਿਉਂਕਿ ਸਾਨੂੰ ਇਕ 2 ਡੀ ਡੀ ਪੀ ਟੇਬਲ ਬਣਾਉਣਾ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਬਹੁਪੱਖੀ ਹੈ.