برنامه یافتن بلندترین زیر رشته جناس قلب — به زبان ساده

۳۳۵ بازدید
آخرین به‌روزرسانی: ۲۰ تیر ۱۴۰۲
زمان مطالعه: ۱۲ دقیقه
برنامه یافتن بلندترین زیر رشته جناس قلب — به زبان ساده

در این مطلب، روش پیدا کردن بلندترین زیر رشته جناس قلب (Longest Palindromic Subsequence) بیان و پیاده‌سازی روش ارائه شده، با استفاده از زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است. در اینجا، یک دنباله داده شده است. هدف، پیدا کردن طول بلندترین زیر رشته جناس قلب برای آن است.

فهرست مطالب این نوشته
997696

بلندترین زیر رشته جناس قلب -- به زبان ساده

به عنوان مثالی دیگر، اگر دنباله داده شده «BBABCBCAB» است، خروجی باید ۷ باشد، زیرا «BABCBAB» بلندترین زیر رشته دارای جناس قلب در این متن است. «BBBBB» و «BBCBB» نیز زیر رشته‌های دارای جناس قلب از دنباله داده شده به عنوان ورودی، هستند؛ اما بلندترین آن‌ها محسوب نمی‌شوند. راهکار ساده برای این مساله، تولید همه زیر دنباله‌ها از یک دنباله داده شده و پیدا کردن بلندترین زیر رشته جناس قلب است. این راهکار دارای پیچیدگی زمانی نمایی است.

ویژگی‌های برنامه‌نویسی پویا در مساله محاسبه بلندترین زیر رشته جناس قلب

در ادامه، بررسی می‌شود که این مساله چگونه هم دارای خصوصیات مهم «برنامه‌نویسی پویا» (Dynamic Programming | DP) است و هم می‌تواند به طور موثری با برنامه‌نویسی پویا حل شود.

  • ساختار بهینه

فرض می‌شود X[0..n-1]‎ دنباله ورودی به طول n و L(0, n-1)‎ طول بلندترین زیر دنباله دارای جناس قلب X[0..n-1]‎ است. اگر اولین و آخرین کاراکترهای X مشابه باشند، داریم: L(0, n-1) = L(1, n-2) + 2؛ در غیر این صورت، L(0, n-1) = MAX (L(1, n-1), L(0, n-2))‎. در ادامه، یک راهکار بازگشتی متداول برای حل این مساله، ارائه شده است.

// Every single character is a palindrome of length 1
L(i, i) = 1 for all indexes i in given sequence

// IF first and last characters are not same
If (X[i] != X[j])  L(i, j) =  max{L(i + 1, j),L(i, j - 1)} 

// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2  

// If there are more than two characters, and first and last 
// characters are same
Else L(i, j) =  L(i + 1, j - 1) + 2

در ادامه، الگوریتم بالا به صورت خط به خط تشریح شده است.

// Every single character is a palindrome of length 1
L(i, i) = 1 for all indexes i in given sequence

هر کاراکتر یکتا، جناس قلبی به طول یک است. برای همه اندیس‌های i در یک دنباله داده شده، L(i, i) = 1 است.

// IF first and last characters are not same
If (X[i] != X[j]) L(i, j) = max{L(i + 1, j),L(i, j - 1)}

اگر اولین و آخرین کاراکتر مشابه نباشند، رابطه بالا برقرار است.

// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2

اگر تنها دو کاراکتر وجود داشته و هر دو نیز مشابه باشند، رابطه بالا برقرار است.

// If there are more than two characters, and first and last 
// characters are same
Else L(i, j) = L(i + 1, j - 1) + 2

اگر بیش از دو کاراکتر وجود داشته باشند و اولین و آخرین کاراکتر مشابه باشند، رابطه بالا برقرار است.

  • زیرمسائل هم‌پوشان

روش بازگشتی یافتن بلندترین زیر رشته جناس قلب

در ادامه، یک پیاده‌سازی کوتاه و بازگشتی از مساله LPS ارائه شده است. پیاده‌سازی این روش، به سادگی و با ساختار بازگشتی بیان شده در بالا، امکان‌پذیر است.

برنامه یافتن بلندترین زیر رشته جناس قلب در ++C به روش بازگشتی

1// C++ program of above approach 
2#include<bits/stdc++.h> 
3using namespace std; 
4  
5// A utility function to get max of two integers 
6int max (int x, int y) { return (x > y)? x : y; } 
7  
8// Returns the length of the longest palindromic subsequence in seq 
9int lps(char *seq, int i, int j) 
10{ 
11// Base Case 1: If there is only 1 character 
12if (i == j) 
13    return 1; 
14  
15// Base Case 2: If there are only 2  
16// characters and both are same 
17if (seq[i] == seq[j] && i + 1 == j) 
18    return 2; 
19  
20// If the first and last characters match 
21if (seq[i] == seq[j]) 
22    return lps (seq, i+1, j-1) + 2; 
23  
24// If the first and last characters do not match 
25return max( lps(seq, i, j-1), lps(seq, i+1, j) ); 
26} 
27  
28/* Driver program to test above functions */
29int main() 
30{ 
31    char seq[] = "GEEKSFORGEEKS"; 
32    int n = strlen(seq); 
33    cout << "The length of the LPS is " 
34         << lps(seq, 0, n-1); 
35    return 0; 
36} 
37  
38// This code is contributed 
39// by Akanksha Rai 

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در C به روش بازگشتی

1// C program of above approach 
2#include<stdio.h> 
3#include<string.h> 
4  
5// A utility function to get max of two integers 
6int max (int x, int y) { return (x > y)? x : y; } 
7  
8// Returns the length of the longest palindromic subsequence in seq 
9int lps(char *seq, int i, int j) 
10{ 
11   // Base Case 1: If there is only 1 character 
12   if (i == j) 
13     return 1; 
14  
15   // Base Case 2: If there are only 2 characters and both are same 
16   if (seq[i] == seq[j] && i + 1 == j) 
17     return 2; 
18  
19   // If the first and last characters match 
20   if (seq[i] == seq[j]) 
21      return lps (seq, i+1, j-1) + 2; 
22  
23   // If the first and last characters do not match 
24   return max( lps(seq, i, j-1), lps(seq, i+1, j) ); 
25} 
26  
27/* Driver program to test above functions */
28int main() 
29{ 
30    char seq[] = "GEEKSFORGEEKS"; 
31    int n = strlen(seq); 
32    printf ("The length of the LPS is %d", lps(seq, 0, n-1)); 
33    getchar(); 
34    return 0; 
35}

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در جاوا به روش بازگشتی

1//Java program of above approach 
2  
3class GFG { 
4  
5    // A utility function to get max of two integers  
6    static int max(int x, int y) { 
7        return (x > y) ? x : y; 
8    } 
9    // Returns the length of the longest palindromic subsequence in seq  
10  
11    static int lps(char seq[], int i, int j) { 
12    // Base Case 1: If there is only 1 character  
13        if (i == j) { 
14            return 1; 
15        } 
16  
17    // Base Case 2: If there are only 2 characters and both are same  
18        if (seq[i] == seq[j] && i + 1 == j) { 
19            return 2; 
20        } 
21  
22    // If the first and last characters match  
23        if (seq[i] == seq[j]) { 
24            return lps(seq, i + 1, j - 1) + 2; 
25        } 
26  
27    // If the first and last characters do not match  
28        return max(lps(seq, i, j - 1), lps(seq, i + 1, j)); 
29    } 
30  
31  
32    /* Driver program to test above function */
33    public static void main(String[] args) { 
34        String seq = "GEEKSFORGEEKS"; 
35        int n = seq.length(); 
36        System.out.printf("The length of the LPS is %d", lps(seq.toCharArray(), 0, n - 1)); 
37  
38    } 
39}

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در پایتون ۳ به روش بازگشتی

1# Python 3 program of above approach 
2  
3# A utility function to get max  
4# of two egers  
5def max(x, y): 
6    if(x > y): 
7        return x 
8    return y 
9      
10# Returns the length of the longest  
11# palindromic subsequence in seq  
12def lps(seq, i, j): 
13      
14    # Base Case 1: If there is  
15    # only 1 character  
16    if (i == j): 
17        return 1
18  
19    # Base Case 2: If there are only 2  
20    # characters and both are same  
21    if (seq[i] == seq[j] and i + 1 == j): 
22        return 2
23      
24    # If the first and last characters match  
25    if (seq[i] == seq[j]): 
26        return lps(seq, i + 1, j - 1) + 2
27  
28    # If the first and last characters 
29    # do not match  
30    return max(lps(seq, i, j - 1),  
31               lps(seq, i + 1, j)) 
32  
33# Driver Code 
34if __name__ == '__main__': 
35    seq = "GEEKSFORGEEKS"
36    n = len(seq) 
37    print("The length of the LPS is",  
38                  lps(seq, 0, n - 1)) 
39      
40# This code contributed by Rajput-Ji

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در سی شارپ به روش بازگشتی

1// C# program of above approach 
2using System; 
3                      
4public class GFG{ 
5  
6    // A utility function to get max of two integers  
7    static int max(int x, int y) { 
8        return (x > y) ? x : y; 
9    } 
10    // Returns the length of the longest palindromic subsequence in seq  
11   
12    static int lps(char []seq, int i, int j) { 
13    // Base Case 1: If there is only 1 character  
14        if (i == j) { 
15            return 1; 
16        } 
17   
18    // Base Case 2: If there are only 2 characters and both are same  
19        if (seq[i] == seq[j] && i + 1 == j) { 
20            return 2; 
21        } 
22   
23    // If the first and last characters match  
24        if (seq[i] == seq[j]) { 
25            return lps(seq, i + 1, j - 1) + 2; 
26        } 
27   
28    // If the first and last characters do not match  
29        return max(lps(seq, i, j - 1), lps(seq, i + 1, j)); 
30    } 
31   
32   
33    /* Driver program to test above function */
34    public static void Main() { 
35        String seq = "GEEKSFORGEEKS"; 
36        int n = seq.Length; 
37        Console.Write("The length of the LPS is "+lps(seq.ToCharArray(), 0, n - 1)); 
38   
39    } 
40} 
41  
42// This code is contributed by Rajput-Ji 

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در PHP به روش بازگشتی

1<?php  
2// PHP program of above approach 
3  
4// Returns the length of the longest 
5// palindromic subsequence in seq 
6function lps($seq, $i, $j) 
7{ 
8      
9    // Base Case 1: If there is 
10    // only 1 character 
11    if ($i == $j) 
12        return 1; 
13      
14    // Base Case 2: If there are only 2  
15    // characters and both are same 
16    if ($seq[$i] == $seq[$j] && $i + 1 == $j) 
17        return 2; 
18      
19    // If the first and last characters match 
20    if ($seq[$i] == $seq[$j]) 
21        return lps ($seq, $i + 1, $j - 1) + 2; 
22      
23    // If the first and last characters 
24    // do not match 
25    return max(lps($seq, $i, $j - 1),  
26               lps($seq, $i + 1, $j)); 
27} 
28  
29// Driver Code 
30$seq = "GEEKSFORGEEKS"; 
31$n = strlen($seq); 
32echo "The length of the LPS is ".  
33            lps($seq, 0, $n - 1); 
34              
35// This code is contributed by ita_c  
36?> 

خروجی قطعه کدهای بالا به صورت زیر است.

The length of the LPS is 5

با در نظر داشتن پیاده‌سازی بالا، در ادامه «درخت بازگشتی جزئی» (Partial Recursion Tree) به طول ۶ با همه کاراکترهای متفاوت آن ارائه شده است.

L(0, 5)
             /        \ 
            /          \  
        L(1,5)          L(0,4)
       /    \            /    \
      /      \          /      \
  L(2,5)    L(1,4)  L(1,4)  L(0,3)

پیدا کردن بلندترین زیر رشته جناس قلب با برنامه‌نویسی پویا

در درخت بازگشتی جزئی که در بخش پیشین ارائه شد، L(1, 4)‎ دو بار حل می‌شود. اگر یک درخت بازگشتی کامل ترسیم شود، می‌توان مشاهده کرد که زیرمسائل بسیاری وجود دارند که دوباره و دوباره حل می‌شوند. از آنجا که مسائل مشابه چند بار فراخوانی می‌شوند، این مساله دارای خصوصیت زیرمسائل هم‌پوشان است.

بنابراین، مساله LPS هر دو خصوصیت مسائل برنامه‌نویسی پویا را دارد. مانند دیگر مسائل مرسوم برنامه‌نویسی پویا، محاسبه مجدد زیر مسائل مشابه با ساخت یک آرایه موقتی L[][]‎ به صورت پایین به بالا قابل انجام است.

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در ++C به روش برنامه‌نویسی پویا

1// A Dynamic Programming based C++ program for LPS problem 
2// Returns the length of the longest palindromic subsequence in seq 
3#include<stdio.h> 
4#include<string.h> 
5  
6// A utility function to get max of two integers 
7int max (int x, int y) { return (x > y)? x : y; } 
8  
9// Returns the length of the longest palindromic subsequence in seq 
10int lps(char *str) 
11{ 
12   int n = strlen(str); 
13   int i, j, cl; 
14   int L[n][n];  // Create a table to store results of subproblems 
15  
16  
17   // Strings of length 1 are palindrome of lentgh 1 
18   for (i = 0; i < n; i++) 
19      L[i][i] = 1; 
20  
21    // Build the table. Note that the lower diagonal values of table are 
22    // useless and not filled in the process. The values are filled in a 
23    // manner similar to Matrix Chain Multiplication DP solution (See 
24    // https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/). cl is length of 
25    // substring 
26    for (cl=2; cl<=n; cl++) 
27    { 
28        for (i=0; i<n-cl+1; i++) 
29        { 
30            j = i+cl-1; 
31            if (str[i] == str[j] && cl == 2) 
32               L[i][j] = 2; 
33            else if (str[i] == str[j]) 
34               L[i][j] = L[i+1][j-1] + 2; 
35            else
36               L[i][j] = max(L[i][j-1], L[i+1][j]); 
37        } 
38    } 
39  
40    return L[0][n-1]; 
41} 
42  
43/* Driver program to test above functions */
44int main() 
45{ 
46    char seq[] = "GEEKS FOR GEEKS"; 
47    int n = strlen(seq); 
48    printf ("The lnegth of the LPS is %d", lps(seq)); 
49    getchar(); 
50    return 0; 
51}

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در جاوا به روش برنامه‌نویسی پویا

1// A Dynamic Programming based Java  
2// Program for the Egg Dropping Puzzle 
3class LPS 
4{ 
5  
6    // A utility function to get max of two integers 
7    static int max (int x, int y) { return (x > y)? x : y; } 
8      
9    // Returns the length of the longest  
10    // palindromic subsequence in seq 
11    static int lps(String seq) 
12    { 
13    int n = seq.length(); 
14    int i, j, cl; 
15    // Create a table to store results of subproblems 
16    int L[][] = new int[n][n];  
17      
18    // Strings of length 1 are palindrome of lentgh 1 
19    for (i = 0; i < n; i++) 
20        L[i][i] = 1; 
21              
22        // Build the table. Note that the lower  
23        // diagonal values of table are 
24        // useless and not filled in the process.  
25        // The values are filled in a manner similar 
26        //  to Matrix Chain Multiplication DP solution (See 
27        // https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/).  
28        // cl is length of substring 
29        for (cl=2; cl<=n; cl++) 
30        { 
31            for (i=0; i<n-cl+1; i++) 
32            { 
33                j = i+cl-1; 
34                if (seq.charAt(i) == seq.charAt(j) && cl == 2) 
35                L[i][j] = 2; 
36                else if (seq.charAt(i) == seq.charAt(j)) 
37                L[i][j] = L[i+1][j-1] + 2; 
38                else
39                L[i][j] = max(L[i][j-1], L[i+1][j]); 
40            } 
41        } 
42              
43        return L[0][n-1]; 
44    } 
45          
46    /* Driver program to test above functions */
47    public static void main(String args[]) 
48    { 
49        String seq = "GEEKSFORGEEKS"; 
50        int n = seq.length(); 
51        System.out.println("The lnegth of the lps is "+ lps(seq)); 
52    } 
53} 
54/* This code is contributed by Rajat Mishra */

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در پایتون به روش برنامه‌نویسی پویا

1# A Dynamic Programming based Python  
2# program for LPS problem Returns the length 
3#  of the longest palindromic subsequence in seq 
4def lps(str): 
5    n = len(str) 
6  
7    # Create a table to store results of subproblems 
8    L = [[0 for x in range(n)] for x in range(n)] 
9  
10    # Strings of length 1 are palindrome of length 1 
11    for i in range(n): 
12        L[i][i] = 1
13  
14    # Build the table. Note that the lower  
15    # diagonal values of table are 
16    # useless and not filled in the process.  
17    # The values are filled in a 
18    # manner similar to Matrix Chain  
19    # Multiplication DP solution (See 
20    # https://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/ 
21    # cl is length of substring 
22    for cl in range(2, n+1): 
23        for i in range(n-cl+1): 
24            j = i+cl-1
25            if str[i] == str[j] and cl == 2: 
26                L[i][j] = 2
27            elif str[i] == str[j]: 
28                L[i][j] = L[i+1][j-1] + 2
29            else: 
30                L[i][j] = max(L[i][j-1], L[i+1][j]); 
31  
32    return L[0][n-1] 
33  
34# Driver program to test above functions 
35seq = "GEEKS FOR GEEKS"
36n = len(seq) 
37print("The length of the LPS is " + str(lps(seq))) 
38  
39# This code is contributed by Bhavya Jain

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در #C به روش برنامه‌نویسی پویا

1// A Dynamic Programming based C# Program 
2// for the Egg Dropping Puzzle 
3using System; 
4  
5class GFG { 
6  
7    // A utility function to get max of 
8    // two integers 
9    static int max (int x, int y)  
10    {  
11        return (x > y)? x : y; 
12    } 
13      
14    // Returns the length of the longest 
15    // palindromic subsequence in seq 
16    static int lps(string seq) 
17    { 
18    int n = seq.Length; 
19    int i, j, cl; 
20      
21    // Create a table to store results 
22    // of subproblems 
23    int [,]L = new int[n,n]; 
24      
25    // Strings of length 1 are  
26    // palindrome of lentgh 1 
27    for (i = 0; i < n; i++) 
28        L[i,i] = 1; 
29              
30        // Build the table. Note that the  
31        // lower diagonal values of table 
32        // are useless and not filled in 
33        // the process. The values are  
34        // filled in a manner similar to 
35        // Matrix Chain Multiplication DP 
36        // solution (See 
37        // https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ 
38        // cl is length of substring 
39        for (cl = 2; cl <= n; cl++) 
40        { 
41            for (i = 0; i < n-cl+1; i++) 
42            { 
43                j = i + cl - 1; 
44                  
45                if (seq[i] == seq[j] && 
46                                  cl == 2) 
47                    L[i,j] = 2; 
48                else if (seq[i] == seq[j]) 
49                    L[i,j] = L[i+1,j-1] + 2; 
50                else
51                    L[i,j] =  
52                     max(L[i,j-1], L[i+1,j]); 
53            } 
54        } 
55              
56        return L[0,n-1]; 
57    } 
58          
59    /* Driver program to test above  
60    functions */
61    public static void Main() 
62    { 
63        string seq = "GEEKS FOR GEEKS"; 
64        int n = seq.Length; 
65        Console.Write("The lnegth of the "
66                  + "lps is "+ lps(seq)); 
67    } 
68} 
69  
70// This code is contributed by nitin mittal.

برنامه پیدا کردن بلندترین زیر رشته جناس قلب در PHP به روش برنامه‌نویسی پویا

1<?php 
2// A Dynamic Programming based  
3// PHP program for LPS problem 
4// Returns the length of the  
5// longest palindromic  
6// subsequence in seq 
7  
8// A utility function to get 
9// max of two integers 
10// function max( $x, $y) 
11// { return ($x > $y)? $x : $y; } 
12  
13// Returns the length of the 
14// longest palindromic  
15// subsequence in seq 
16function lps($str) 
17{ 
18$n = strlen($str); 
19$i; $j; $cl; 
20  
21// Create a table to store 
22// results of subproblems 
23$L[][] = array(array());  
24  
25  
26// Strings of length 1 are 
27// palindrome of lentgh 1 
28for ($i = 0; $i < $n; $i++) 
29    $L[$i][$i] = 1; 
30  
31    // Build the table. Note that  
32    // the lower diagonal values  
33    // of table are useless and  
34    // not filled in the process.  
35    // The values are filled in a  
36    // manner similar to Matrix  
37    // Chain Multiplication DP  
38    // solution (See  
39    // https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/). 
40    // cl is length of substring 
41    for ($cl = 2; $cl <= $n; $cl++) 
42    { 
43        for ($i = 0; $i < $n - $cl + 1; $i++) 
44        { 
45            $j = $i + $cl - 1; 
46            if ($str[$i] == $str[$j] &&  
47                            $cl == 2) 
48            $L[$i][$j] = 2; 
49            else if ($str[$i] == $str[$j]) 
50            $L[$i][$j] = $L[$i + 1][$j - 1] + 2; 
51            else
52            $L[$i][$j] = max($L[$i][$j - 1],  
53                             $L[$i + 1][$j]); 
54        } 
55    } 
56  
57    return $L[0][$n - 1]; 
58} 
59  
60// Driver Code 
61$seq = 'GEEKS FOR GEEKS'; 
62$n = strlen($seq); 
63echo "The lnegth of the " .  
64      "LPS is ", lps($seq); 
65  
66// This code is contributed 
67// by shiv_bhakt. 
68?>

خروجی قطعه کدهای بالا به صورت زیر است.

The lnegth of the LPS is 7

پیچیدگی زمانی پیاده‌سازی بالا از درجه O(n2)‎ است. این میزان، از پیچیدگی زمانی بدترین حالت پیاده‌سازی بازگشتی ساده نیز بهتر است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۲ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۱ دیدگاه برای «برنامه یافتن بلندترین زیر رشته جناس قلب — به زبان ساده»

salam . mamnun az etelaatetun . mikhastam bedunam chetor mishe hamzaman ba be dast avordan e toole LPS , khod e un ro ham be dast ovord ? yani alave bar tulesh , khod e subsequence ro ham dar biarim.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *