You are not logged in. Please login at www.codechef.com to post your questions!

×

Finding all palindromes in String

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 apprecatedThanks :-)

//string palindrome search

include<stdio.h>

include<iostream>

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;
                }
            }
        }
    }
}

}

This question is marked "community wiki".

asked 20 Aug '13, 19:20

nabil1997's gravatar image

3★nabil1997
11111716
accept rate: 0%

edited 20 Aug '13, 19:23


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. :) I hope this will help. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.3022&rep=rep1&type=pdf

link

answered 21 Aug '13, 01:32

arnabbcs08's gravatar image

4★arnabbcs08
99359
accept rate: 0%

Thanks man,,It comes with good details and is really easy enough..Thanks a lot :-)

(21 Aug '13, 20:13) nabil19973★
link

answered 21 Aug '13, 09:57

hkbharath's gravatar image

3★hkbharath
1492714
accept rate: 9%

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.

link

answered 02 Nov '16, 17:12

ashleyrubin's gravatar image

0★ashleyrubin
1
accept rate: 0%

include<stdio.h> include<iostream> 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;
            }
        }
    }
}

} }

link

answered 29 Jul '17, 10:18

elnino_09's gravatar image

2★elnino_09
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,911
×1,655
×640
×195

question asked: 20 Aug '13, 19:20

question was seen: 25,305 times

last updated: 29 Jul '17, 10:18