Let R be a sequence. The inverse sequence of R is the sequence
by reading the symbols in R backwards. For example, the inverse of
0113 is 3110. If the inverse of R is identical to R, then R is
called a palindrome sequence. For example, R[9] = 011303110 is a
palindrome sequence. Given a sequence S, if R is a subsequence of S
and R is palindrome, then R is called a palindrome subsequence of
S. One can then similarly define what a longest palindrome
subsequence (LPS for short) of S is.
Problem:
Write a program that reads in a sequence of max length = 10,000. Then compute the LPS of a sequence input by the user. Output will print the LPS and its length.
Sample run:
Enter a sequence: 13112301728031631251841324
# an LPS (length = 13) for the second sequence is:
3112136312113
Solution:
/* C program to find the the longest palindromic substring */
#include <stdio.h> //for standard I/O
#include <stdbool.h> //for boolean variable
#include <string.h> //for string functions strlen
// function to find the longest palindromic substring and
//print the substring & its length
int longestPalinStr(char str[])
{
// find the length of the input string
int n = strlen(str);
//array for memoization
bool array[n][n];
//declare array as false(0) initially
memset(array, 0, sizeof(array));
//length of 1 character substring
int maxLen = 1;
//for length 1 substring set true(1)
for (int k = 0; k < n; k++)
array[k][k] = true;
//checking for substring of length 2.
int start = 0;
for (int i = 0; i < n-1; i++)
{
if (str[i] == str[i+1])
{
array[i][i+1] = true;
start = i;
maxLen = 2;
}
}
//loop for substrings of lengths > 2
for (int k = 3; k <= n; k++)
{
for (int i = 0; i < n-k+1 ; i++)
{
//for last index
int j = i + k - 1;
//check for the contained substring to be palindrome
//using array[i+1][j-1] and boundary characters using str[i] and str[j]
if (array[i+1][j-1] && str[i] == str[j])
{
//if above 'if' is true then set position of array[i][j] to be true
array[i][j] = true;
//to set position of start
//and update maxLen
if (k > maxLen)
{
maxLen = k;
start = i;
}
}
}
}
printf(" The longest palindromic substring is: ");
int last = start + maxLen - 1;
//print the substring from start index to last index
for( int i = start; i <= last; i++ )
printf("%c",str[i]);
printf("\nLength is: %d" , maxLen);
}
//main function
int main()
{
//decalre a character array of size 10000
char ch[10000];
//read the string from console
scanf("%s",&ch);
//call thelongestPalinStr() to find the longest palindromic substring of ch[]
longestPalinStr(ch);
return 0;
}
Problem:
Write a program that reads in a sequence of max length = 10,000. Then compute the LPS of a sequence input by the user. Output will print the LPS and its length.
Sample run:
Enter a sequence: 13112301728031631251841324
# an LPS (length = 13) for the second sequence is:
3112136312113
Solution:
/* C program to find the the longest palindromic substring */
#include <stdio.h> //for standard I/O
#include <stdbool.h> //for boolean variable
#include <string.h> //for string functions strlen
// function to find the longest palindromic substring and
//print the substring & its length
int longestPalinStr(char str[])
{
// find the length of the input string
int n = strlen(str);
//array for memoization
bool array[n][n];
//declare array as false(0) initially
memset(array, 0, sizeof(array));
//length of 1 character substring
int maxLen = 1;
//for length 1 substring set true(1)
for (int k = 0; k < n; k++)
array[k][k] = true;
//checking for substring of length 2.
int start = 0;
for (int i = 0; i < n-1; i++)
{
if (str[i] == str[i+1])
{
array[i][i+1] = true;
start = i;
maxLen = 2;
}
}
//loop for substrings of lengths > 2
for (int k = 3; k <= n; k++)
{
for (int i = 0; i < n-k+1 ; i++)
{
//for last index
int j = i + k - 1;
//check for the contained substring to be palindrome
//using array[i+1][j-1] and boundary characters using str[i] and str[j]
if (array[i+1][j-1] && str[i] == str[j])
{
//if above 'if' is true then set position of array[i][j] to be true
array[i][j] = true;
//to set position of start
//and update maxLen
if (k > maxLen)
{
maxLen = k;
start = i;
}
}
}
}
printf(" The longest palindromic substring is: ");
int last = start + maxLen - 1;
//print the substring from start index to last index
for( int i = start; i <= last; i++ )
printf("%c",str[i]);
printf("\nLength is: %d" , maxLen);
}
//main function
int main()
{
//decalre a character array of size 10000
char ch[10000];
//read the string from console
scanf("%s",&ch);
//call thelongestPalinStr() to find the longest palindromic substring of ch[]
longestPalinStr(ch);
return 0;
}
