המשך הפלינדרומי הארוך ביותר


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית פייסבוק מיקרוסופט
תכנות דינמי מחרוזת

בבעיית ההמשך הפלינדרומית הארוכה ביותר נתנו מחרוזת, מצא את אורך המשך הפלינדרומי הארוך ביותר.

דוגמאות

קלט:
TUTORIALCUP
פלט:
3

קלט:
תכנות דינמי
פלט:
7

המשך הפלינדרומי הארוך ביותר

גישה נאיבית להמשך הפלינדרומי הארוך ביותר

הגישה הנאיבית לפתרון הבעיה שלעיל היא ליצור את כל המשכים של המחרוזת הנתונה ולמצוא את אורך ההמשך הפלינדרומי הארוך ביותר.
מורכבות הזמן היא מעריכי, שהוא גבוה מאוד.

גישה אופטימלית להמשך הפלינדרומי הארוך ביותר

הבעיה שלעיל כוללת מבנה אופטימלי ותכונה חופפת, כך תכנות דינמי יכול לשמש לפיתרון הבעיה.
תן שאורך המחרוזת / ים הנתון יהיה n, ואורך המשך הפלינדרומי הארוך ביותר עבור s יוצג כ- LPS (s, 0, n - 1).
s -> מחרוזת נתונה
0 -> אינדקס התחלתי
n - 1 -> אינדקס סיום

  • אם התווים הראשונים והאחרונים של s (מחרוזת נתונה) זהים, אז,
    LPS (s, 0, n - 1) = 2 + LPS (s, 1, n - 2)
  • אַחֵר,
    LPS (s, 0, n - 1) = מקסימום (LPS (s, 0, n - 2), LPS (s, 1, n - 1))
  • מקרה יסוד : מיתרים באורך 1 הם תמיד פלנדרום, כלומר LPS (s, i, i) = 1
  • מקרה יסוד : אם יש שתי תווים במחרוזת ושתיהן זהות, אז מדובר בפלינדרום.

באמצעות רקורסיה וזכירה זו אנו יכולים למצוא את ה- LPS במורכבות זמן טובה יותר.

אַלגוֹרִיתְם

  1. צור מערך דו-ממדי lps בגודל (n X n), כאשר n הוא אורך המחרוזת s, הוא מאחסן את אורך ההמשך הפלינדרומי הארוך ביותר מ- x ל- y, כאשר x הוא מספר השורה ו- y הוא מספר העמודה והתשובה לבעיה הנ"ל היא LPS [2] [n - 0].
  2. ניתן לנו מחרוזות s, אינדקס ההתחלה i ו- index e.
  3. אם i ו- e שווים, החזר 1 (מקרה בסיס).
  4. אם i + 1 = e והתווים ב- i ו- e ב- s זהים, החזר 2 (מקרה בסיס).
  5. אחרת אם תווים במיקום i ו- e במחרוזת s שווים להחזיר 2 + LPS (s, i + 1, e - 1).
  6. החזר אחר מקסימלי (LPS (s, i + 1, e), LPS (s, i, e - 1)).
  7. לפני ביצוע שיחה רקורסיבית כלשהי, בדוק את הערך המתאים במערך lps, כלומר LPS (s, i, e) קיים ב- lps [i] [e], אם אין ערך במערך lps בצע שיחה רקורסיבית אחרת השתמש בערך המחושב. שלב זה אחראי להפחתת מורכבות הזמן של האלגוריתם.

מורכבות זמן = O (n ^ 2)

קוד JAVA להמשך הפלינדרומי הארוך ביותר

public class LongestPalindromicSubsequence {

    // Function to return the length of longest palindromic subsequence
    private static int LPS(String s) {
        int n = s.length();
        int[][] lps = new int[n][n];

        return lpsUtil(s.toCharArray(), 0, n - 1, lps);
    }

    // Recursive utility function to calculate the length of longest palindromic subsequence
    private static int lpsUtil(char[] s, int i, int e, int[][] lps) {
        // Return if already calculated
        if (lps[i][e] != 0) {
            return lps[i][e];
        }

        // Base case (String of length 1 is always a palindrome)
        if (i == e) {
            lps[i][e] = 1;
            return 1;
        }

        // Base Case (If there are only 2 characters and both are same)
        if (s[i] == s[e] && i + 1 == e) {
            lps[i][e] = 2;
            return 2;
        }

        // If first and last characters are same then
        // LPS(s, i, e) = 2 + LPS(s, i + 1, e - 1)
        if (s[i] == s[e]) {
            // If not calculated before, find the result and store in lps array
            if (lps[i + 1][e - 1] == 0) {
                lps[i + 1][e - 1] = lpsUtil(s, i + 1, e - 1, lps);
            }

            // Store the result in lps array
            lps[i][e] = 2 + lps[i + 1][e - 1];
            return lps[i][e];
        } else {
            // If not calculated before, find the result and store in lps array
            if (lps[i + 1][e] == 0) {
                lps[i + 1][e] = lpsUtil(s, i + 1, e, lps);
            }
            // If not calculated before, find the result and store in lps array
            if (lps[i][e - 1] == 0) {
                lps[i][e - 1] = lpsUtil(s, i, e - 1, lps);
            }

            // Store the result in lps array
            lps[i][e] = Math.max(lps[i + 1][e], lps[i][e - 1]);
            return lps[i][e];
        }
    }

    public static void main(String[] args) {
        // Example 1
        System.out.println(LPS("TUTORIALCUP"));

        // Example 2
        System.out.println(LPS("DYNAMICPROGRAMMING"));
    }
}

קוד C + + להמשך הפלינדרומי הארוך ביותר

#include <bits/stdc++.h>
#define MAXN 1000
using namespace std;

// Global array to store the lps for a given string
int lps[MAXN][MAXN];

// Recursive utility function to calculate the length of longest palindromic subsequence
int lpsUtil(string s, int i, int e) {
    // Return if already calculated
    if (lps[i][e] != 0) {
        return lps[i][e];
    }
    
    // Base case (String of length 1 is always a palindrome)
    if (i == e) {
        lps[i][e] = 1;
        return 1;
    }
    
    // Base Case (If there are only 2 characters and both are same)
    if (s[i] == s[e] && i + 1 == e) {
        lps[i][e] = 2;
        return 2;
    }
    
    // If first and last characters are same then
    // LPS(s, i, e) = 2 + LPS(s, i + 1, e - 1)
    if (s[i] == s[e]) {
        // If not calculated before, find the result and store in lps array
        if (lps[i + 1][e - 1] == 0) {
            lps[i + 1][e - 1] = lpsUtil(s, i + 1, e - 1);
        }
        
        // Store the result in lps array
        lps[i][e] = 2 + lps[i + 1][e - 1];
        return lps[i][e];
    } else {
        // If not calculated before, find the result and store in lps array
        if (lps[i + 1][e] == 0) {
            lps[i + 1][e] = lpsUtil(s, i + 1, e);
        }
        // If not calculated before, find the result and store in lps array
        if (lps[i][e - 1] == 0) {
            lps[i][e - 1] = lpsUtil(s, i, e - 1);
        }

        // Store the result in lps array
        lps[i][e] = std::max(lps[i + 1][e], lps[i][e - 1]);
        return lps[i][e];
    }
}

// Function to return the length of longest palindromic subsequence
int LPS(string s) {
    int n = s.length();
    
    // Initialise lps as 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            lps[i][j] = 0;
        }
    }
    
    return lpsUtil(s, 0, n - 1);
}

int main() {
    // Example 1
    cout<<LPS("TUTORIALCUP")<<endl;
    
    // Example 2
    cout<<LPS("DYNAMICPROGRAMMING")<<endl;
    
    return 0;
}
3
7

הפניות