CareerCup

Let s be the input string, and R(s) be the reversal of the string.
compute the suffix tree of s#R(s)$, which can be done in linear time.
Any node whose subtree contains both # and $ corresponds to a palindrome.

<pre lang="java" line="1" title="CodeMonkey19298" class="run-this">class AllPalindromes {

public static void main(String args[]){
//input a string
String args1="ramukumar";
//exit if less than length 2
if(args1.length() < 2)
{
System.exit(0);
}
boolean b=checkPalin(args1);

System.out.println (args1 +" is " +(b? "":" not ") + "a palindrome" );

for (int i=0;i<args1.length();i++){
for (int j=i+2;j<args1.length();j++){
String substr=args1.substring(i,j);

if(checkPalin(substr)){
System.out.println(substr+ " is a substring");}
else{
System.out.println(substr+ " is not a substring");}
}
}




}

public static boolean checkPalin(String args) {
int half =args.length()/2;
int length=args.length();
char arr[]=args.toCharArray();
for(int i=0;i<half;i++){
if (arr[i] != arr[length -1 - i])
return false;
}
return true;
}


}</pre><pre title="CodeMonkey19298" input="yes">
</pre>

Take advantage of the fact that if abba is palindrome then bb too, so:

Find all the occurrences of the form: aa or aba
in the string. These occurrences are the center of the palindrome. You create a list of this indexes in linear time.

Then for each of these indexes add the solution already found (either aa or aba) and check if adding one character on each side is also a solution. In the worst case you will do it n / 2 times where n is the length of the string and you will do it k times where k is the number of indexes found (k <= n / 2).

So the total time is f(n) = n + (n / 2) * k which is O(n * k) time

public static bool isPolindrome(string strInput)
{
if (string.IsNullOrEmpty(strInput))
return false;

bool isPolindrome = true;

int i = 0, j = strInput.Length - 1;
while (i < j)
{
if (strInput[i++] != strInput[j--])
return !isPolindrome;
}
return isPolindrome;
}

Use Stack to get O(n)
Read each char.. compare with stackTop
If same, it is part of palindrome, Pop the stacktop to compare the next char with the previous character.
else add it to stack.

public class Palindrome {

		public static void main(String[] args) {
		String s = "123abba3426jjgf";
		printPalindromes(s);
		
	}

	private static void printPalindromes(String s) {
		int n = s.length();
		char c;
		
		//Stack will hold all the characters in the String
		Stack<Character> charStack = new Stack<Character>();
		StringBuffer palindrome = null;
		for(int i=0; i < n ; i++) {
			c = s.charAt(i);
			if(charStack.isEmpty()) {
				charStack.add(c);
			} else {
				if(c==charStack.peek()) {
					
					/* if current char matches then there is a Palindrome 
					 * Pop the stacktop so that previous char can be compared 
					 * with the next char
					 * */
					charStack.pop();
					
					if(palindrome!=null) {
						/*Insert at the beginning of Palindrome */
						palindrome.insert(0, c);
						/*Insert at the end of Palindrome */
						palindrome.append(c);
						
					} else {
						/*Create a Palindrome */
						palindrome = new StringBuffer();
						palindrome.append(c);
						palindrome.append(c);
					}
					/*
					 * Handle boundary conditions when last letter is part of 
					 * palindrome and stack is not empty. 
					 * */
					if(charStack.isEmpty() || i==n-1) {
						System.out.println(palindrome);
						palindrome = null;
					}
					
				} else {
					if(palindrome!=null) {
						System.out.println(palindrome);
						palindrome = null;
					} 
					charStack.add(c);
				}
			}
			
		}
		
	}
	
	

}

It can be done as a modification of manacher algorithm. 

string preprocess(string s)
{
	int n=s.length();
	if(n==0) return "^$";
	string ret="^";
	for(int i=0;i<n;i++)
		ret+="#"+s.substr(i,1);
	ret+="#$";
	return ret;
}

void manacher(string s)
	{
		t=preprocess(s);
		int p=new int[t.length()];
		int c=0,r=0;
		p[0]=0;
		for(int i=1;i<t.length()-1;i++)
		{
			mirror=2*i-c;
			p[i]=R>i?min(R-i,p[mirror]):0;
			while(t[i-p[i]-1]==t[i+1+p[i]]) p[i]++;
			if(i+p[i]>R)
			{
				c=i;
				R=i+p[i];
			}
		}
		for(int i=0;i<t.length;i++)
		{
			if(p[i]>=4)
			{
				printf(s.substring((i-1-p[i])/2,p[i]/2);
			}
		}
	}

manacher algorithm is okay ,
and suffix array is also okay