Find all possible palindromes in a string using C

Question

I have written a program to find all the possible palindromes in the string. The code is below

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
  clrscr();
  char *ptr1;
  char str[100];
  printf("enter the string with even length\n");
  gets(str);
  int n;
  int i=strlen(str);
  if(i%2==0)
  {
    for(int n=0;n<=strlen(str);n++)
    {
      for(int k=1;k<=strlen(str);k++)
      {
        int m=0;
        int j=0;
        ptr1=str;
        while(*ptr1!='\0')
        {
          ptr1+;
          j++;
          m++;
        }
        j=j-k;
        for(i=n;i<m/2;i++,j--)
        {
          if(str[i]!=str[j])
          {
            break;
          }
        }
        if(j<=i)
          printf("String is a palindrome\n");
        else
          printf("String is not a palindrome\n");
      }
    }
  }
  else
  {
    printf("String is of odd length");
  }
  getch();
}

But the number of print statements I am getting is more than what it needs to display. Can anyone help me out with the code and tell me where have i gone wrong with this.

Answer 1

I'm not sure if there would be an easy way to find "all possible" palindromes in a string. Several considerations and assumptions will be required:

(1) Minimum and Maximum length of each substring that we want to grill. Or else, every single character would be a palindrome in itself! Maximum of course being a number (one?) less than the string length

(2) Before we choose a substring, should we stick to the original arrangement of characters (as per the given input)? Or, should the program first generate the possible permutations by itself and then inspect the strings thus obtained.

(3) To make it more complex, if an input character occurs twice (or more), then there will be at least two (or more) substrings with the similar arrangement of characters. This will require additional logic to curb the duplicates... (array of strings)

I strongly feel that what's narrated above should be quite superfluous to the "actual" requirement that you might have. However, coming back to the root of the problem of inspecting a palindrome, think that a two pointer approach could be an easy as well as less resource extensive solution. For example (illustrated with a static input):

char str[10] = "rotator";
int str_length = strlen(str);
int palindrome_flag = 1;
char *ptr1 = str;
char *ptr2 = ptr1 + str_length - 1;

while(ptr1 <= ptr2){
    if(*ptr1 != *ptr2){
        palindrome_flag = 0;
        break;
    }

    ptr1++;
    ptr2--;
}

if(palindrome_flag){
    printf("\n String \"%s\" is a palindrome", str);
}
else{
    printf("\n String \"%s\" is not a palindrome", str);
}

return 0;

Hope this helps? Thank you.

Answer 2

This code seems like working, but there is still scope for improvement. Logic is simple, checking palindrome inside palindrome. Keep two count. keep one count constant and increment another count. Check these two counts characters are the same. If we dont find same then exit and increment another counter. Once the second counter reaches end, increment the first counter and second counter +1 of first counter.

#include <stdio.h>
#include <string.h>

int main()
{
        int i, j, k, p, count, m, found;
        char str[20];

        k = p = count = m = found = 0;

        printf("enter a string\n");
        scanf("%s", str);
        printf("string %s\n", str);
        printf("length %d\n", strlen(str));

        for (i = 0; i < strlen(str); i++) {
                for (j = i + 1; j < strlen(str); j++) {
                        for (k = i, p = j; k <= p; k++, p--) {

                                if (str[k] == str[p])
                                        found = 1;
                                else {
                                        found = 0;
                                        break;
                                }
                        }
                        if (found) {
                                count++;
                                printf("found count %d\n", count);
                        }
                }
        }
        printf("-- count = %d\n", count);

        return 0;
    }