برنامه یافتن بلندترین زیر رشته جناس قلب — به زبان ساده
در این مطلب، روش پیدا کردن بلندترین زیر رشته جناس قلب (Longest Palindromic Subsequence) بیان و پیادهسازی روش ارائه شده، با استفاده از زبانهای برنامهنویسی گوناگون شامل «سیپلاسپلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پیاچپی» (PHP) انجام شده است. در اینجا، یک دنباله داده شده است. هدف، پیدا کردن طول بلندترین زیر رشته جناس قلب برای آن است.
به عنوان مثالی دیگر، اگر دنباله داده شده «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) است. این میزان، از پیچیدگی زمانی بدترین حالت پیادهسازی بازگشتی ساده نیز بهتر است.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی پایتون
- آموزش تکمیلی برنامهنویسی پایتون
- مجموعه آموزشهای دادهکاوی و یادگیری ماشین
- زبان برنامهنویسی پایتون (Python) — از صفر تا صد
- یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
- آموزش پایتون (Python) — مجموعه مقالات جامع وبلاگ فرادرس
^^
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.