மிக நீண்ட மீண்டும் மீண்டும்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆர்சீசியம் 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), ஏனெனில் இந்த அணுகுமுறை மிக நீண்ட பொதுவான அடுத்தடுத்த சிக்கலைப் போன்றது. இதனால் நேர சிக்கலும் அதற்கு ஒத்ததாகும்.

விண்வெளி சிக்கலானது

ஓ (என் ^ 2), ஏனெனில் நாம் 2 டி டிபி அட்டவணையை உருவாக்க வேண்டும். இதனால் விண்வெளி சிக்கலானது பல்லுறுப்புக்கோவையாகும்.