CareerCup

Yeah its working here is the code. You can test it. Just keep a track of max palindrome substring occured so far and also take two pointers low and high and if the substring is palindrome and high-low+1 is greater than max so far then update max and print the substring:

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
void print(char *str,int low,int high){
int i;
for(i=low;i<=high;i++)
printf("%c",str[i]);
}
int longsub(char *str){
int maxl=1,start=0,i,low,high;
int n=strlen(str);
for(i=1;i<n;i++){
    //for odd palindrome
   low=i-1;high=i;
while(low>=0&&high<n&&str[low]==str[high]){
     if(high-low+1>maxl){
       start=low;
       maxl=high-low+1;
     }
    --low;++high;
}
//for even palindrome
low=i-1;high=i+1;
while(low>=0&&high<n&&str[low]==str[high]){
    if(high-low+1>maxl){
    start=low;
    maxl=high-low+1;
    }
    --low;++high;
}
}
printf("Longest Palindrome substring is is ");
print(str,start,start+maxl-1);
}
int main()
{    char str[] = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
    printf("\nLength is: %d\n", longsub( str ) );
    return 0;
}

In Pseudocode:

FindPalindrome(String S)
{
  for(int len = s.size, len > 0; --len)
  {
  
  }
}

Sorry - hit submit by accident.
This algo searches for the longest possible strings first, then iterates downwards till it hits zero. If zero, it outputs nothing.

Again in pseudo:

FindReverse(String s)
{
 for(int l = s.size; l > 0; --l)
   for(int st = 0; st + l < s.size; ++st)
     if(IsPalindrome(s.substring(st, len))
        return s.substring(st, len); 
}

bool IsPalindrome(String s)
{
  int i = 0; 
  while(I < (s.length - (I + 1))
  {
    if(s[I] != s[s.length - (I + 1)])
      return false;
    ++I;
  }
  return true;
}

String findLonguestPalindrome(String s) {
		String result = "";
		for(int i = 0 ; i < (s.length() - 1) ; i++) {

			if(s.charAt(i) == s.charAt(i + 1)) {
				String candidate = extractPalindrome(s, i, i+1, "");
				if(candidate.length() > result.length())
					result = candidate;
			}
			
			if(i > 0 && s.charAt(i - 1) == s.charAt(i + 1)) {
				String candidate = extractPalindrome(s, i - 1, i+1, "" + s.charAt(i));
				if(candidate.length() > result.length())
					result = candidate;
			}
		}
		return result;
	}

	String extractPalindrome(String s, int left, int right, String base) {
		while( left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right))
		{
			base = s.charAt(left) + base + s.charAt(right);
			left--;
			right++;	
		}
		return base;
	}

A dynamic algo solution :

/* 
Find the longest substring that is the same in reverse. 

As an example, if the input was "I like racecars that go fast" 
the answer would be "racecar". 

Test your code in the following String:


"FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"

Developed By : Suman Roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<string>
using namespace std;
typedef struct node{
       char c_value;
       int i_count;
}node;
void Print( node ** array , int i_size ){
	for( int i=0; i<i_size ; i++){
		for (int j=0 ; j<i_size ; j++ ){
			std::cout<<array[i][j].c_value<<":"<<array[i][j].i_count<<"   ";
		}
		std::cout<<std::endl;
	}
}

void Find( node **array , int i_length ){
	int i_max=0;
	int x,y;
	for( int i=1; i< i_length ; i++){
		for( int j=1 ; j<i_length ; j++){
			if ( array[0][j].c_value == array[i][0].c_value ){
				array[i][j].i_count=array[i-1][j-1].i_count + 1;
				if( array[i][j].i_count >i_max ){
					i_max=array[i][j].i_count;
					x=i;y=j;
				}
			}

			}
	}
	std::cout<<i_max<<std::endl;
	std::cout<<x<<y<<std::endl;
	std::cout<<"Maximum substring is \n";
	while( ( x>=0 ) & ( y>= 0 ) & ( array[x][y].i_count > 0 ) ){
		std::cout<<array[0][y--].c_value;
		x--;
	}
	std::cout<<std::endl;
//	Print( array , i_length);
}

int main(){
	string s_value="I like racecars that go fast";
	//std::cin>>s_value;
	int i_length=s_value.length();
	i_length ++;
	int j=1;
	node **array=new node* [ i_length  ];
	for( int i=0 ; i <i_length ; i++ ){
		array[ i ]=new node [ i_length ];
	}
	
	for( std::string::iterator ii =s_value.begin () ; ii!=s_value.end() ;ii++ ){
		array[0][j].i_count=0;
		array[0][j++].c_value=*ii;
	}
	j=1;
	for( std::string::reverse_iterator ii=s_value.rbegin() ; ii!=s_value.rend() ; ii ++ ){
		array[j][0].i_count=0;
		array[j++][0].c_value=*ii;
	}
		array[0][0].i_count=0;
		//Print( array , i_length );
		
	Find(array , i_length );

//	Print( array , i_length );
}

Output:

1. ( for 1st string )
suman@suman-laptop:/media/D/coding/algo/Dynamic$ ./a.out
Maximum substring is
racecar

2.(for long string)
suman@suman-laptop:/media/D/coding/algo/Dynamic$ ./a.out
Maximum substring is
ranynar

Below is the java program
package com.bala.logical;

public class Polindrome {
	public static void main(String[] args) {
		String bigString = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
		String bigPoli = "";
		for (int i = 0; i < bigString.length(); i++) {
			for (int j = i + 1; j < bigString.length(); j++) {
				String s = bigString.substring(i, j);
				if (isPolindrome(s)) {
					if (s.length() > bigPoli.length()) {
						bigPoli = s;
					}
				}
			}
		}
		System.out.println(bigPoli);
	}

	public static boolean isPolindrome(String s) {
		String a = "";
		for (int i = s.length() - 1; i >= 0; i--) {
			a = a + s.charAt(i);
		}
		if (s.equals(a)) {
			return true;
		}
		return false;
	}

	
}
  output: ranynar

One other solution:

/** Find the theLongest substring that is the same in reverse. */
public class App {

    public static class Palindrome {

        private final String text;
        private String theLongest;


        public Palindrome(/*@Nonnull*/ String text) {
            this.text = text;
        }


        public String getTheLongest() {
            if (theLongest == null) {
                theLongest = searchForLongest();
            }
            return theLongest;
        }


        private String searchForLongest() {
            String result = "";
            int textLength = text.length();

            for (int i = 0; i < textLength; i++) {
                for (int j = textLength - 1; j > i; j--) {
                    if (isTheSameChars(i, j) && isPalindrome(i, j)) {
                        result = getMax(result, text.substring(i, j + 1));
                        break;
                    }
                }
            }

            return result;
        }

        private boolean isTheSameChars(int indexA, int indexB) {
            return text.charAt(indexA) == text.charAt(indexB);
        }

        private boolean isPalindrome(int start, int end) {
            if (start >= end) {
                return false;
            }

            for (int i = start, j = end; i < j; i++, j--) {
                if (text.charAt(i) != text.charAt(j)) {
                    return false;
                }
            }

            return true;
        }

        private String getMax(/*@Nonnull*/ String textA, /*@Nonnull*/ String textB) {
            return textA.length() >= textB.length() ? textA : textB;
        }

    }


    public static final String TEST_STRING =
        "Fourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnati"
        + "onconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatede"
        + "qualNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynart"
        + "ionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemld"
        + "oftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplace"
        + "forthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfang"
        + "andproperthatweshoulddothisButinalargersensewecannotdedicatewecannotco"
        + "nsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledh"
        + "erehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfi"
        + "lllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydi"
        + "dhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhic"
        + "htheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobehereded"
        + "icatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakei"
        + "ncreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevoti"
        + "onthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisna"
        + "tionunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeopleby"
        + "thepeopleforthepeopleshallnotperishfromtheearth";


    public static void main(String[] args) {
        Palindrome palindrome = new Palindrome(TEST_STRING);
        String result = palindrome.getTheLongest();

        System.out.println("The longest palindrome: " + result);
    }

}

Guys, I got a more clear solution for this. Just add a boolean for mode.

oh any one knows how to add tab??

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class ReverseData
{
public:
int low;
int high;
ReverseData():low(0),high(0)
{
}
};

void longest_sub(char* s);

int main(int argc, char* argv[])
{
char str[] = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";

longest_sub(str);

int i;
cin>>i;
return 0;
}

void longest_sub(char* s)
{
vector<ReverseData*> myQueue;
bool reverseMode = false;
ReverseData* p;
int longest = 0;
int longestidx = -1;

size_t l = strlen(s);
for (int i = 1; i < l; i++)
{
if (!reverseMode)
{
if (s[i] == s[i-1])
{
reverseMode = true;
p = new ReverseData();
p->low = i -1;
p->high = i;
}
}
else
{
if (s[i] == s[p->low-1])
{
p->low--;
p->high = i;
}
else
{
myQueue.push_back(p);
reverseMode = false;
longest = max(longest, (p->high-p->low)+1);
if (longest == (p->high-p->low)+1)
longestidx = myQueue.size()-1;
}
}
}

if (longestidx>=0)
{
for (int i = myQueue[longestidx]->low; i <= myQueue[longestidx]->high; i++)
cout<<s[i];
cout<<endl;
}

}

public class Palindrome {
	public static int findLargest(int[] numbers)
	{  
	    int largest = numbers[0];  
	    for(int i = 1; i < numbers.length; i++){  
	        if(numbers[i] > largest){  
	            largest = numbers[i];  
	        }  
	    }  
	    return largest;
	}
	
	public static int findLargestIndex(int[] numbers)
	{  
	    int largest = numbers[0]; 
	    int index = 0;
	    int i;
	    for(i = 1; i < numbers.length; i++){  
	        if(numbers[i] > largest){  
	            largest = numbers[i];
	            index = i;
	        }  
	    }  
	    return index;
	}
	
	public static String getLongestPalindrome(String str)
	{
		StringBuffer tmp = new StringBuffer(str);
		StringBuffer reversedStr = tmp.reverse();
		char[] buffer = new char[str.length()];
		reversedStr.getChars(0, str.length(), buffer, 0);
		int [] sizes = new int[str.length()];
		for (int i = 0; i < str.length() - 2; i++)
		{
			int start = i;
			int end = i + 2;
			int count = 0;
			CharSequence s = reversedStr.subSequence(start, end);	
			while (str.contains(s))
			{
				count ++;
				s = reversedStr.subSequence(start, end + count);
			}
			sizes [i] = count;		
		}
		int largest = findLargest(sizes);
		int index = findLargestIndex(sizes);
		return reversedStr.substring(index, index + largest +1);		
	}
	
	    
	public static void main (String[] args)
	{
	    	String substr = getLongestPalindrome("I like racecars that go fast");
	    	System.out.println(substr);
	    	
	}

}

This code should work in O(n) time.

public static String longestPalindrome(String str) 
{ 
	int last = -1;
	int maxStart = 0, maxEnd = 0;
		
	char input[] = str.toCharArray();
	for (int i = 1 ; i < input.length ; i++) {
		char currentChar = input[i];
		if (last > 0) {
			if (currentChar == input[last-1]) {
				last--;
				if (i - last > maxEnd - maxStart) {
					maxStart = last;
					maxEnd = i;
				}
			} else {
				last = -1;
			}
		} 
		if (last == -1) {
			if (i < input.length - 1 && currentChar == input[i+1]) {
				last = i;
				while (i < input.length - 1 && currentChar == input[i+1]) {
					i++;
				}
			} else if (i > 1 && currentChar == input[i-2]) {
				last = i-2;
				if (i - last > maxEnd - maxStart) {
					maxStart = last;
					maxEnd = i;
				}
			}
		}
	}
	
	String answer = new String(input, maxStart, maxEnd - maxStart + 1);
	
	return answer;
}