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

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 

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 

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?> 

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 */