Finding all palindromes in String

general
, , ,
1

It’s my code to find all palindromes in string (2 characters or more),But I know it ain’t a good piece.How can I optimize this code or is there any efficient algorithm for this type of problems.(Finding all Palindromes in Strings)…And I think for some cases it is also not giving me correct output…I’m not getting that…!..
Any help d be apprecated Thanks :slight_smile:

//string palindrome search
#include<stdio.h>

#include

#include<string.h>

using namespace std;

int main()

{

char input[100];


char modified[100]="";

//This ll be modified form only with alphabets

cout<<“Enter text:\n”;

gets(input);


int t=strlen(input);

int s=0;

for(int e=0;e<t;e++)

{

    if(islower(input[e]))

    {

        modified[s] =input[e];

        s++;

    }
}

printf("\nThe modified version of the text is:");

puts(modified);

int l=strlen(modified);

for(int a=0;a<(l-1);a++)

    for(int b=a+1;b<l;b++)

{


    if(modified[a]==modified[b])
    {
        if((b-a)%2==0) //even
        {
            int x=(a+b)/2;
            int countt=0;
            for(int p=a,q=b;p<x && q>x;p++,q--)
            {
                if(modified[p]==modified[q])
                    countt++;

                else if(modified[p]!=modified[q])
                    break;

                if(countt==(b-a)/2)
                {
                    cout<<"Palindrome:";
                    for(int i=a;i<=b;i++)
                    {
                        putchar(modified[i]);
                    }
                    cout<<endl;
                }
            }
        }

        else if((b-a)%2!=0) //odd
        {
            int y=(a+b+1)/2;
            int z=(a+b-1)/2;
            int count2=0;
            for(int w=a,r=b;w<y && r>z ;w++,r--)
            {
                                    if(modified[w]==modified[r])
                    count2++;

                else if(modified[w]!=modified[r])
                    break;

                if(count2==(b-a+1)/2)
                {
                    cout<<"Palindrome:";
                    for(int o=a;o<=b;o++)
                    {
                        putchar(modified[o]);
                    }
                    cout<<endl;
                }
            }
        }
    }
}

}

2

Are you trying to find all palindromic substrings or palindromic subsequnces?

Let me answer both,
Palindromic Substring - There exists a non trivial(proof) but easy to code O(n) Manacher’s algorithm for this one which finds the longest palindrome centred at any index of the string. Using that this can be done in O(n) time.

Palindromic Subsequnce - There is an O(n^3) algorithm which I googled about after seeing your question. :slight_smile: I hope this will help.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.3022&rep=rep1&type=pdf

1 Like
3

This link may help you

http://discuss.codechef.com/questions/21607/palindrome-string-c-suggestion-for-optimization
4

Thanks man,It comes with good details and is really easy enough…Thanks a lot :slight_smile:

5

I am expecting the dialect is English for the information and I am printing each conceivable print utilizing characters depending on their utilization than particular, courseworklabs for unmistakable palindromes utilize a set for the outcomes.
So Let’s discussion about palindromes to begin with, They are symmetric about their revolves either around a letter in the center case abbbbcbbbba which bases on c or like abba which bases on between the a large portion of the length of the string.

6

include<stdio.h>
include
include<string.h>
using namespace std;

int main()

{

char input[100];

char modified[100]="";
//This ll be modified form only with alphabets

cout<<“Enter text:\n”;

gets(input);

int t=strlen(input);
int s=0;

for(int e=0;e<t;e++)

{

if(islower(input[e]))

{

    modified[s] =input[e];

    s++;

}

}
printf("\nThe modified version of the text is:");

puts(modified);
int l=strlen(modified);

for(int a=0;a<(l-1);a++)

for(int b=a+1;b<l;b++)

{

if(modified[a]==modified[b])
{
    if((b-a)%2==0) //even
    {
        int x=(a+b)/2;
        int countt=0;
        for(int p=a,q=b;p<x && q>x;p++,q--)
        {
            if(modified[p]==modified[q])
                countt++;

            else if(modified[p]!=modified[q])
                break;

            if(countt==(b-a)/2)
            {
                cout<<"Palindrome:";
                for(int i=a;i<=b;i++)
                {
                    putchar(modified[i]);
                }
                cout<<endl;
            }
        }
    }

    else if((b-a)%2!=0) //odd
    {
        int y=(a+b+1)/2;
        int z=(a+b-1)/2;
        int count2=0;
        for(int w=a,r=b;w<y && r>z ;w++,r--)
        {
                                if(modified[w]==modified[r])
                count2++;

            else if(modified[w]!=modified[r])
                break;

            if(count2==(b-a+1)/2)
            {
                cout<<"Palindrome:";
                for(int o=a;o<=b;o++)
                {
                    putchar(modified[o]);
                }
                cout<<endl;
            }
        }
    }
}

}
}