Write pseudocode for an algorithm that accepts a string (or character array) str

Question

Write pseudocode for an algorithm that accepts a string (or character array) str as its input and returns the longest substring of str that happens to be a palindrome. Recall that a palindrome is a string that, when reversed, equals itself. Examples of palindromes include "dad", "abcdededcba", "m", "ii", and "noon." If a string contains multiple palindrome substrings of maximal length, then your algorithm may return any of these substrings. Your algorithm should have best-case runtime of O(n) and worst case runtime of O(n^2). Your algorithm should use constant O(1) storage. Given an example of a string that yields best-case performance and an example of a string that yields worst case performance.

Explanation / Answer

#include <stdio.h>

#include <string.h>

// A utility function to print a substring str[low..high]

void printSubStr( char* str, int low, int high )

{

for( int i = low; i <= high; ++i )

printf("%c", str[i]);

}

// This function prints the longest palindrome substring

// of str[].

// It also returns the length of the longest palindrome

int longestPalSubstr( char *str )

{

int n = strlen( str ); // get length of input string

// table[i][j] will be false if substring str[i..j]

// is not palindrome.

// Else table[i][j] will be true

bool table[n][n];

memset(table, 0, sizeof(table));

// All substrings of length 1 are palindromes

int maxLength = 1;

for (int i = 0; i < n; ++i)

table[i][i] = true;

// check for sub-string of length 2.

int start = 0;

for (int i = 0; i < n-1; ++i)

{

if (str[i] == str[i+1])

{

table[i][i+1] = true;

start = i;

maxLength = 2;

}

}

// Check for lengths greater than 2. k is length

// of substring

for (int k = 3; k <= n; ++k)

{

// Fix the starting index

for (int i = 0; i < n-k+1 ; ++i)

{

// Get the ending index of substring from

// starting index i and length k

int j = i + k - 1;

// checking for sub-string from ith index to

// jth index iff str[i+1] to str[j-1] is a

// palindrome

if (table[i+1][j-1] && str[i] == str[j])

{

table[i][j] = true;

if (k > maxLength)

{

start = i;

maxLength = k;

}

}

}

}

printf("Longest palindrome substring is: ");

printSubStr( str, start, start + maxLength - 1 );

return maxLength; // return length of LPS

}

// Driver program to test above functions

int main()

{

char str[255] = scanf("%s", str);

printf(" Length is: %d ", longestPalSubstr( str ) );

return 0;

}

The above code meets all your requirements. Have a great day.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.