Finding the largest palindrome in string implementation

I'm trying to solve a problem that asks to find the largest palindrome in a string up to 20,000 characters. I've tried to check every sub string whether it's a palindrome, that worked, but obviously was too slow. After a little googling I found this nice algorithm http://stevekrenzel.com/articles/longest-palnidrome. I've tried to implement it, however I can't get it to work. Also the given string contains illegal characters, so I have to convert it to only legal characters and output the longest palindrome with all characters.

Here's my attempt:

int len = original.length(); int longest = 0; string answer; for (int i = 0; i < len-1; i++){ int lower(0), upper(0); if (len % 2 == 0){ lower = i; upper = i+1; } else { lower = i; upper = i; } while (lower >= 0 && upper <= len){ string s2 = original.substr(lower,upper-lower+1); string s = convert(s2); if (s[0] == s[s.length()-1]){ lower -= 1; upper += 1; } else { if (s.length() > longest){ longest = s.length(); answer = s2; } break; } } }

I can't get it to work, I've tried using this exact algorithm on paper and it worked, please help. Here's full code if you need it : http://pastebin.com/sSskr3GY

EDIT:

int longest = 0; string answer; string converted = convert(original); int len = converted.length(); if (len % 2 == 0){ for (int i = 0; i < len - 1; i++){ int lower(i),upper(i+1); while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){ lower -= 1; upper += 1; } string s = converted.substr(lower+1,upper-lower-1); if (s.length() > longest){ longest = s.length(); answer = s; } } } else { for (int i = 0; i < len; i++){ int lower(i), upper(i); while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){ lower -= 1; upper += 1; } string s = converted.substr(lower+1,upper-lower-1); if (s.length() > longest){ longest = s.length(); answer = s; } } }

Okay so I fixed the problems, it works perfectly fine but only if the length of converted string is odd. Please help.

-------------Problems Reply------------

I can see two major errors:

  1. Whether you initialise your upper/lower pointers to i,i or i,i+1 depends on the parity of the palindrome's length you want to find, not the original string. So (without any further optimisations) you'll need two separate loops with i going from 0 to len (len-1), one for odd palindrome lengths and another one for even.
  2. The algorithms should be executed on the converted string only. You have to convert the original string first for it to work.

Consider this string: abc^ba (where ^ is an illegal character), the longest palindrome excluding illegal characters is clearly abcba, but when you get to i==2, and move your lower/upper bounds out by one, they will define the bc^ substring, after conversion it becomes bc, and b != c so you concede this palindrome can't be extended.

#include <iostream>
using namespace std;

int main()
{

string s;
cin >> s;
signed int i=1;
signed int k=0;
int ml=0;
int mi=0;
bool f=0;

while(i<s.length())
{
if(s[i]!=s[i+1])
{
for(k=1;;k++)
{
if(!(s[i-k]==s[i+k] && (i-k)>=0 && (i+k)<s.length()))
{
break;
}
else if(ml < k)
{
ml=k;
mi=i;
f=1;
}
}
}
i++;
}

i=0;

while(i<s.length())
{
if(s[i]==s[i+1])
{
for(k=1;;k++)
{
if(!(s[i-k]==s[k+1+i] && (i-k)>=0 && (k+i)<s.length()))
{
break;
}
else if(ml < k)
{
ml=k;
mi=i;
}
}
}
i++;
}

if(ml < 1)
{
cout << "No Planidrom found";
return 0;
}

if(f==0)
{
cout << s.substr(mi-ml,2*ml+2);
}
else
{
cout << s.substr(mi-ml,2*ml+1);
}

return 0;

}

@biziclop : As you said.. i used 2 while loops. one for even and one for old palindrom string. finally i was able to fix it. thanks for your suggestion.

Category:c# Views:1 Time:2011-03-14

Related post

  • Finding the largest palindrome of the product of two three digit numbers problem 2010-07-14

    So on Project Euler the Problem 4 states the following: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99. Find the largest palindrome made from the product of two 3-dig

  • Find the largest palindrome made from the product of two 3-digit numbers 2011-08-25

    package testing.project; public class PalindromeThreeDigits { public static void main(String[] args) { int value = 0; for(int i = 100;i <=999;i++) { for(int j = i;j <=999;j++) { int value1 = i * j; StringBuilder sb1 = new StringBuilder(""+value

  • Efficient String Implementation in Haskell 2009-02-23

    I'm currently teaching myself Haskell, and I'm wondering what the best practices are when working with strings in Haskell. The default string implementation in Haskell is a list of Char. This is inefficient for file input-output, according to Real Wo

  • How is std::string implemented? 2009-09-23

    I am curious to know how std::string is implemented and how does it differ from c string?If the standard does not specify any implementation then any implementation with explanation would be great with how it satisfies the string requirement given by

  • Adding formatting support to a custom string implementation - C 2010-10-09

    I have a C application (not using C99 features) that does some heavy string processing. Since the string lengths are not known, statically allocated buffers is not an option for me. I have created a simple string implementation which will abstract th

  • How do I know which STL string implementation I'm using? 2011-03-28

    Item 15 of Effective STL says that there are at least 6 different implementations of std::string. But if I have to be aware of which implementation I'm using, how do I find out which implementation I'm using? std::string of gcc does not show the sour

  • Largest Palindrome of two digit numbers 2011-09-21

    The program below is to find palindromes in products of 2 digit numbers (up to 10*11 for trails). #include<iostream> using namespace std; int res1=0 void palindrome(int mul) { int k,res=0,count=0; int p=mul; while(mul!=0) { k=mul%10; res=(res*1

  • Switching on a string/implementing button actions 2008-10-08

    Full disclaimer: I'm a CS student, and this question is related to a recently assigned Java program for Object-Oriented Programming. Although we've done some console stuff, this is the first time we've worked with a GUI and Swing or Awt. We were give

  • One more string implementation in C: advantages and disadvantages 2009-11-26

    After reading the article "Back to Basics" by Mr.Spolsky I have thought about string structure in C, that converges most of advantages of Pascal-style string (with length byte) and classic ASCIIZ-strings in C and reduces most of their disadvantages.

  • std::string implementation in GCC and its memory overhead for short strings 2011-02-20

    I am currently working on an application for a low-memory platform that requires an std::set of many short strings (>100,000 strings of 4-16 characters each). I recently transitioned this set from std::string to const char * to save memory and I w

  • My Simple String Implementation Gone Wrong 2011-04-01

    I am creating my simple implementation of the String class like in the .Net framework. The only difference, it is less sugary if you know what I am mean. Anyhow, I got it everything to work except for the overloaded operators for the + operator; whic

  • palindrome of string gets segmentation fault 2011-10-15

    Just for fun I have written a function to check if string given is palindrome. When I run the prog it throws segmentation fault. Could anyone please throw light on it. int palindrome( const char *input ) { char * reverse; int len = 0 ; int i = 0; boo

  • A custom string implementation to overload operators > for a binary shift of string characters in c# 2012-04-14

    I would like to know how to implement a MyString class in c# and overloading operators << and >>. For example : MyString name = "string"; Console.Write(name<<3) // It will print **ingstr** by shifting last 3 to left My current imple

  • C++11 constexpr string implementation 2012-05-02

    Is there a way to implement strings to work both at compile time and run time? AFAIK for a class to be constexpr constructed it needs to have a trivial destructor. However, this proves difficult when we're dealing with strings. If the string is NOT c

  • Comparing strings excluding punctuation and whitespace 2012-04-26

    I'm making a program to find the larges palindrome in C++ and I need to get the palindromes for the inputted strings ignoring the case, punctuation and whitespace. For example, see the following line: Confusius say: Madam, I'm Adam. Here, the largest

  • A better algorithm to find the next palindrome of a number string 2011-10-28

    Firstly here is the problem: A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write

  • How to check if the given string is palindrome? 2008-09-09

    Definition: A palindrome is a word, phrase, number or other sequence of units that has the property of reading the same in either direction How to check if the given string is a palindrome? This was one of the FAIQ [Frequently Asked Interview Questio

  • How to check that a string is a palindrome using regular expressions? 2008-10-24

    That was an interview question that I was unable to answer: How to check that a string is a palindrome using regular expressions? p.s. There is already a question "How to check if the given string is palindrome?" and it gives a lot of answers in diff

  • Need some help in writing a recursive implementation for my Palindrome app 2011-03-27

    First of all I am not asking for people to "do my homework" like I have seen others on here ask for. I have managed to code a working iterative version of a program that determines if a string is a palindrome or not. Spaces, punctuation and special c

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.281 (s). 11 q(s)