أطول نتيجة متكررة


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Arcesium Avalara ByteDance عاصمة واحدة Facebook [متليف
بحث ثنائي البرمجة الديناميكية مزيج خيط

تنص مشكلة "أطول تكرار متكرر" على أنه تم إعطاؤك سلسلة كمدخل. اكتشف أطول تتابع متكرر ، أي التتابع الذي يوجد مرتين في السلسلة.

مثال

أطول نتيجة متكررة

aeafbdfdg
3 (afd)

الرسالة

تطلب منا المشكلة معرفة أطول تكرار متكرر في السلسلة. للتذكر ، اللاحقة هي سلسلة تبقى لك إذا حذفت بعض الأحرف من السلسلة. لذلك ، يمكن أن يكون النهج الساذج هو توليد كل التكرارات اللاحقة. بعد إنشاء ما يليه ، نبدأ في التحقق مما إذا كان أي من التكرارات اللاحقة يلبي متطلباتنا أم لا. لكن توليد التالي هو عملية تستغرق وقتًا طويلاً. وبالتالي نحن بحاجة إلى التفكير في أي نهج آخر بدلاً من توليد التكرارات اللاحقة.

الشيء الآخر الذي يمكننا القيام به هو الاستخدام البرمجة الديناميكية. المشكلة هي اختلاف طفيف على أطول نتيجة مشتركة. هناك نوعان من التغييرات. أولاً ، بدلاً من سلسلتين ، نحن نعمل على سلسلة واحدة. والشيء الآخر مرتبط أيضًا بالحقيقة الأولى. نظرًا لأننا نعمل على سلسلة واحدة ونريد تكرار السلسلة اللاحقة. نطلب تحديد الأحرف التي يجب أن تكون مستقلة بشكل حصري في كل من التتابعات اللاحقة التي يجب أن يكون فهرس الأحرف مختلفًا. لذا من الناحية الرسمية ، سنقوم باستدعاء نفس الوظيفة للعثور على أطول سلسلة متتالية مشتركة ولكن بدلاً من تمرير السلسلة الثانية. نقوم بتمرير نفس السلسلة مثل الوسيطة الأولى والثانية بشرط أن يكون فهرس نفس الأحرف مختلفًا.

كود 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

تحليل التعقيد

تعقيد الوقت

يا (N ^ 2) ، لأن هذا النهج هو نفس نهج مشكلة التتابع الأكثر شيوعًا. وبالتالي فإن التعقيد الزمني مشابه لذلك.

تعقيد الفضاء

يا (N ^ 2) ، لأنه يتعين علينا إنشاء جدول ثنائي الأبعاد DP. وبالتالي فإن تعقيد الفضاء هو أيضًا متعدد الحدود.