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:

- 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.
- 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.