Find longest palindrome in text

palindrome.cpp

/*
 * Find the longest palindrome in the text.
 *
 * This is Greplin's first challenge, and I originally solved it in Python.
 *
 * The algorithm is not optimal, but simple on the eyes and easy to understand
 * On big inputs it's possible to use an approximately linear algorithm.
 *
 * Christian Stigen Larsen
 */

#include <stdio.h>

static const char text[] =
  "Fourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnati"
  "onconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequ"
  "alNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartions"
  "oconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzha"
  "twarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthose"
  "whoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandpropert"
  "hatweshoulddothisButinalargersensewecannotdedicatewecannotconsecrateweca"
  "nnothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecr"
  "ateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenor"
  "longrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthel"
  "ivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughthereha"
  "vethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafsk"
  "remainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatca"
  "useforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvet"
  "hatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbi"
  "rthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotp"
  "erishfromtheearth";

inline bool is_palindrome(const char* l, const char* r)
{
  while ( *l==*r && l<=r )
    ++l, --r;

  return l>r;
}

int main()
{
  const char *end = text + sizeof(text);
  size_t best = 0;

  for ( const char *l = text; l<end; ++l )
    for ( const char *r = l+1+best; r<end; ++r )
      if ( is_palindrome(l, r) )
        printf("%.*s\n", (best=r-l)+1, l);

  return 0;
}

You can do this linearly by traversing text once. To find palindromes, for each character, expand left and right as long as they are equal.

Code showing this idea can be found at https://gist.github.com/851611