ഏറ്റവും ദൈർഘ്യമേറിയ ആവർത്തനം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആർസെസിയം അവലാര ബൈറ്റ്ഡാൻസ് ക്യാപിറ്റൽ വൺ ഫേസ്ബുക്ക് മെറ്റ്ലൈഫ്
ബൈനറി തിരയൽ ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ഹാഷ് സ്ട്രിംഗ്

“ദൈർഘ്യമേറിയ ആവർത്തിച്ചുള്ള തുടർച്ച” എന്ന പ്രശ്നം ഒരു ഇൻപുട്ടായി നിങ്ങൾക്ക് ഒരു സ്‌ട്രിംഗ് നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു. ഏറ്റവും ദൈർഘ്യമേറിയ ആവർത്തിച്ചുള്ള കണ്ടെത്തൽ കണ്ടെത്തുക, അതാണ് സ്ട്രിംഗിൽ രണ്ടുതവണ നിലനിൽക്കുന്നത്.

ഉദാഹരണം

ഏറ്റവും ദൈർഘ്യമേറിയ ആവർത്തനം

aeafbdfdg
3 (afd)

സമീപനം

സ്‌ട്രിംഗിലെ ഏറ്റവും ദൈർഘ്യമേറിയ തുടർച്ചയെ കണ്ടെത്താൻ പ്രശ്‌നം ഞങ്ങളോട് ആവശ്യപ്പെടുന്നു. ഓർമ്മിക്കാൻ, സ്ട്രിംഗിൽ നിന്ന് ചില പ്രതീകങ്ങൾ ഇല്ലാതാക്കുകയാണെങ്കിൽ നിങ്ങൾക്ക് ശേഷിക്കുന്ന ഒരു സ്ട്രിംഗാണ് തുടർന്നുള്ളത്. അതിനാൽ, നിഷ്കളങ്കമായ ഒരു സമീപനം എല്ലാ തുടർന്നുള്ള തലമുറകളായിരിക്കാം. തുടർന്നുള്ള തലമുറയ്ക്ക് ശേഷം, ഏതെങ്കിലും തുടർന്നുള്ളവ നമ്മുടെ ആവശ്യകത നിറവേറ്റുന്നുണ്ടോ എന്ന് പരിശോധിക്കാൻ ആരംഭിക്കുന്നു. എന്നാൽ ഒരു തുടർന്നുള്ള തലമുറ സമയമെടുക്കുന്ന പ്രക്രിയയാണ്. അങ്ങനെ തുടർന്നുള്ളവ സൃഷ്ടിക്കുന്നതിനുപകരം മറ്റേതെങ്കിലും സമീപനത്തെക്കുറിച്ച് ചിന്തിക്കേണ്ടതുണ്ട്.

നമുക്ക് ചെയ്യാൻ കഴിയുന്ന മറ്റൊരു കാര്യം ഉപയോഗമാണ് ഡൈനാമിക് പ്രോഗ്രാമിംഗ്. എന്നതിലെ ഒരു ചെറിയ വ്യതിയാനമാണ് പ്രശ്നം ഏറ്റവും ദൈർഘ്യമേറിയ പൊതുവായ തുടർച്ച. രണ്ട് മാറ്റങ്ങളുണ്ട്. ആദ്യം, രണ്ട് സ്ട്രിംഗുകൾക്ക് പകരം, ഞങ്ങൾ ഒരൊറ്റ സ്ട്രിംഗിലാണ് പ്രവർത്തിക്കുന്നത്. മറ്റൊന്ന് ആദ്യത്തെ വസ്തുതയുമായി ബന്ധപ്പെട്ടിരിക്കുന്നു. ഞങ്ങൾ ഒരൊറ്റ സ്ട്രിംഗിൽ പ്രവർത്തിക്കുന്നതിനാൽ തുടർന്നുള്ള കാര്യങ്ങൾ ആവർത്തിക്കണമെന്ന് ഞങ്ങൾ ആഗ്രഹിക്കുന്നു. പ്രതീകങ്ങളുടെ സൂചികയായ തുടർന്നുള്ള രണ്ടിലും പ്രത്യേകമായി സ്വതന്ത്രമായ പ്രതീകങ്ങൾ തിരഞ്ഞെടുക്കേണ്ടതുണ്ട്. കൂടുതൽ formal പചാരികമായി പറഞ്ഞാൽ, ഏറ്റവും ദൈർഘ്യമേറിയ പൊതുവായ തുടർച്ച കണ്ടെത്തുന്നതിന് ഞങ്ങൾ അതേ ഫംഗ്ഷനെ വിളിക്കും, പക്ഷേ രണ്ടാമത്തെ സ്ട്രിംഗ് കടന്നുപോകുന്നതിന് പകരം. ഒന്നാമത്തെയും രണ്ടാമത്തെയും ആർഗ്യുമെന്റിന്റെ അതേ സ്ട്രിംഗ് ഞങ്ങൾ ഒരേ പ്രതീകങ്ങളുടെ സൂചിക വ്യത്യസ്തമായിരിക്കണം എന്ന നിബന്ധനയോടെ കടന്നുപോകുന്നു.

ഏറ്റവും ദൈർഘ്യമേറിയ ആവർത്തിച്ചുള്ള കണ്ടെത്തൽ കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#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), കാരണം ഞങ്ങൾ ഒരു 2 ഡി ഡിപി പട്ടിക സൃഷ്ടിക്കണം. അതിനാൽ ബഹിരാകാശ സങ്കീർണ്ണതയും പോളിനോമിയൽ ആണ്.