Find largest palindromic substrings in a string

Question

I have written some code to find the largest palindromic sub-strings in a string without repeating any character.

Example input

abappabaxhhh

output

abappaba
x
hhh

---

The code

#include <stdio.h>
#include <string.h>
int is_palendrome(char *arr,int n,int l,int r)
{
 while(r>l)
 {
 
 if(arr[l++]!=arr[r--])
 return 0;
 
 }
 return 1;
}
int bps(char *arr,int n,int r, int l)
{
 if(l==n)
 return 0;
 int x=0;
 if(is_palendrome(arr,n,l,r))
 {
 x=1;
 for(int i=l;i<=r;i++)
 {
 printf("%c",arr[i]);
 }
 printf("\n");
 }
 if(x==1)
 {
 x=0;
 l=r+1;
 bps(arr,n,n,l);
 }
 else
 {
 r--;
 x=0;
 bps(arr,n,r,l);
 }
}
void main()
{
 char array[3][3];
 char arr[]="abappabaxhhh";//abaaa
 int n=strlen(arr);
 bps(arr,n,n-1,0);
}

Answer 1

int is_palendrome(char *arr,int n,int l,int r)

Spelling: palindrome

Consider including <stdbool.h> and returning a bool value.

The arguments could do with more descriptive names. It's particularly unclear what n is for, as it appears to be unused within the function.

Why does arr point to modifiable char? I think we should pass const char*.

l and r might be better as size_t values (include <stdint.h>) since they are used to index a string. Alternatively, we could just pass a pair of pointers:

#include <stdbool.h>
bool is_palindrome(const char *left, const char *right)
{
 while (left < right) {
 if (*left++ != *right--)
 return false;
 }
 return true;
}

---

int bps(char *arr,int n,int r, int l)

This one could do with a better name. And we should document what it returns. In fact, at present, it's missing a return statement, so that needs fixing.

if(l==n)
return 0;
int x=0;

That indentation style is unhelpful. It's possibly caused by pasting tab characters into Stack Exchange (which has tab-stops every 4 characters, unlike most terminals). That's a good reason to use spaces for indentation (or, like Linux sources, use a full tab for each indent level).

The variable x which remembers which branch of the if we took doesn't add value - just move the if (x==1) code into those branches:

if(is_palendrome(arr,n,l,r))
{
 /* x=1; */
 ...
 l = r+1;
 r = n;
} else {
 --r;
}
bps(arr,n,r,l);

 for(int i=l;i<=r;i++)
 {
 printf("%c",arr[i]);
 }
 printf("\n");

Performing our output within the function limits its usefulness. We're not able to do anything else with the results in a future program.

Also, we don't need to write a loop to print a substring - we can do that with %s conversion by passing a precision specification like this:

 printf("%.*s\n", r+1-l, arr+l);

---

The signature of the main function should be int main(void) - Standard C does not permit main() with a void return type. However, the magic of main() is that you don't need to write a return statement - if omitted, then main() (and only main()) will return a success value (zero).

The variable array seems unused.

---

Changing the interface

To use the results more flexibly, I would write the function to return the length of the longest initial palindrome. That way, the caller can choose what to do with it, and whether to continue looking at the rest of the string.

#include <stdbool.h>
bool is_palindrome(const char *left, const char *right)
{
 while (left < right) {
 if (*left++ != *right--)
 return false;
 }
 return true;
}
/* Returns the length of the longest palindrome anchored to the
 beginning of the string. This will be zero if the string is
 empty.
 */
size_t longest_initial_palindrome(const char* s)
{
 size_t len = strlen(s);
 while (len && !is_palindrome(s, s + len - 1)) {
 --len;
 }
 return len;
}

For example, here's a program that processes each of its arguments, and enumerates the palindromes therein:

#include <stdio.h>
int main(int argc, char **argv)
{
 for (int i = 1; i < argc; ++i) {
 const char *s = argv[i];
 printf("\n%s:\n", s);
 size_t index = 0;
 size_t pal_len;
 while ((pal_len = longest_initial_palindrome(s))) {
 printf("%zu: %.*s\n", ++index, (int)pal_len, s);
 s += pal_len;
 }
 }
}

---

Algorithm

The program doesn't work as advertised. For example, input abaccccab should find longest palindromic substring baccccab, and so split a/baccccab. Instead, it starts from the left, and splits as aba/cccc/a/b.

Fixing that problem is left as an exercise.

• user786: This should be my masters thesis topic. I did not solve it. Still trying. There are whole research topics and papers on palendromic substring is this true. Is it this complex?
• Toby Speight: Yes, I wrote "left as an exercise" somewhat tongue-in-cheek! It would seem to be a difficult problem.
• Yonlif: Yes it is complex (The fastest method I am familiar with is using an LCS tree), if you are trying to solve is as a masters thesis I would highly recommend not to write code. Get yourself a paper and a pen and calculate the time complexity with a fully figured out algorithm. Good luck :)

Answer 2

Description

"Finds largest palindromic sub-strings in a string without repeating any character"? Sure? Maybe "splits the string into the palindromic substrings"? Because, say, "ababba" would be spited into "aba", "bb", "a" - not "a", "b", "abba" to have the largest palindromic substring.

Indentation

Wrong indentation makes code unreadable. It's hard to code when you struggle to read your own code. Most IDEs have tools to indent the code; make use of them.

Identifiers

What are arr, n, l, r? Is it array you're working with or the string represented as array? Is n the length of that string or something else? l and r seem to be left and right... or not? What is bps? is_palendrome - is the mistake in "palindrome" intentional to show... what? Good names save a lot of time on reading the code.

Arguments order

You have two functions with the same argument names and types, but in a different order. Why? Besides, is_palendrome doesn't use n.

Function return type

bps is declared with int return type, but it returns 0 only in one situation, and that value is never used. Maybe it should be void?

Extra variable x

x is set in the if expression and checked right after it. Why?

This does the same, and saves several lines:

if(is_palendrome(arr,n,l,r))
{
 for(int i=l;i<=r;i++)
 {
 printf("%c",arr[i]);
 }
 printf("\n");
 l=r+1;
 bps(arr,n,n,l);
}
else
{
 r--;
 bps(arr,n,r,l);
}

Unnecessary recursion

The only recursive call to bps happens as the last action of the function - so, bps starts over. You can change it into a while loop.

• user786: X is not extra. See the code
• user786: I respectfully disagree on number of things but Thanks for the answer.
• Toby Speight: Not only IDEs have reformatters - there are some good free-standing ones too, such as GNU Indent.