Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. http://oj.leetcode.com/problems/longest-palindromic-substring/

LongestPalindrome.cpp

// LongestPalindromic.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <string>
#include <iostream>

using namespace std;

class Solution 
{
public:
	string longestPalindrome(string s) 
	{
		int i, l, r;
		int n = s.length();
		int resultL, resultR;
		resultL = resultR = 0;

		if ((n == 0) || (n == 1))
		{
			return s;
		}

		for (i = 0; i < n; i++)
		{
			l = r = i;
			while (l >= 0 && r <= n - 1)
			{
				if (s[l] == s[r])
				{
					l--;
					r++;
				}
				else
				{
					l++;
					r--;
					break;
				}
			}

			if (l < 0)
			{
				l = 0;
				r--;
			}

			if (r > n - 1)
			{
				l++;
				r = n - 1;
			}

			if (r - l > resultR - resultL)
			{
				resultL = l;
				resultR = r;
			}
		}

		for (i = 0; i < n - 1; i++)
		{
			l = i;
			r = i + 1;

			if (s[l] != s[r])
				continue;

			while (l >= 0 && r <= n - 1)
			{
				if (s[l] == s[r])
				{
					l--;
					r++;
				}
				else
				{
					l++;
					r--;
					break;
				}
			}

			if (l < 0)
			{
				l = 0;
				r--;
			}

			if (r > n - 1)
			{
				l++;
				r = n - 1;
			}

			if (r - l > resultR - resultL)
			{
				resultL = l;
				resultR = r;
			}
		}

		return s.substr(resultL, resultR - resultL + 1);
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	Solution s;
	string input;
	string output;

	input = "";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "a";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "ab";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "aaa";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "aba";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "aaaa";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "abab";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "abba";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "cdefgggabccccbazyz";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "abcabcabc";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "ecccccccccccccccb";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "abaabaaba";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	input = "";
	output = s.longestPalindrome(input);
	cout << input << endl << output << endl << endl;

	return 0;
}