title: Finding the largest palindrome in string implementation
body: <p>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 
  <a href="http://stevekrenzel.com/articles/longest-palnidrome" rel="nofollow">http://stevekrenzel.com/articles/longest-palnidrome</a>. 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.</p>
  
  <p>Here's my attempt:</p>
  
  <pre><code>int len = original.length();
  int longest = 0;
  string answer;
  
  for (int i = 0; i &lt; len-1; i++){
  
      int lower(0), upper(0);
  
      if (len % 2 == 0){
          lower = i;
          upper = i+1;
      } else {
          lower = i;
          upper = i;
      }
  
      while (lower &gt;= 0 &amp;&amp; upper &lt;= 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() &gt; longest){
                  longest = s.length();
                  answer = s2;
              }
              break;
          }
  
  
      }
  }
  </code></pre>
  
  <p>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 : <a href="http://pastebin.com/sSskr3GY" rel="nofollow">http://pastebin.com/sSskr3GY</a> </p>
  
  <p><strong>EDIT:</strong></p>
  
  <pre><code>int longest = 0;
  string answer;
  string converted = convert(original);
  int len = converted.length();
  
  if (len % 2 == 0){
      for (int i = 0; i &lt; len - 1; i++){
          int lower(i),upper(i+1);
          while (lower &gt;= 0 &amp;&amp; upper &lt;= len &amp;&amp; converted[lower] == converted[upper]){
              lower -= 1;
              upper += 1;
          }
          string s = converted.substr(lower+1,upper-lower-1);
          if (s.length() &gt; longest){
              longest = s.length();
              answer = s;
          }
      }
  } else {
      for (int i = 0; i &lt; len; i++){
          int lower(i), upper(i);
          while (lower &gt;= 0 &amp;&amp; upper &lt;= len &amp;&amp; converted[lower] == converted[upper]){
              lower -= 1;
              upper += 1;
          }
          string s = converted.substr(lower+1,upper-lower-1);
          if (s.length() &gt; longest){
              longest = s.length();
              answer = s;
          }
      }
  }
  </code></pre>
  
  <p>Okay so I fixed the problems, it works perfectly fine but only if the length of converted string is odd. Please help.</p>