CareerCup

Use Manacer's algorithm to find them in O(n)

public class ManacherLongestPalindromicSubstring{

	public static String preprocess(String in){
		StringBuffer sb = new StringBuffer();
			sb.append’#’);
		for(int i=0; i<in.length(); i++){
			sb.append(in.charAt(i));
			sb.append(‘#’);
		}
		return sb.toString();
	}

	public static String LongestPalindrome(String in){

	/*Preprocess the string to insert special character  ‘#’ in the spaced between characters in input and the two outside edges. This is done merely to make the computation identical for both odd and even length input string. */

		String S = preprocess(in);
		int C = 0; //contains center of current palindrome
		int R = 0; //contains the right edge of current palindrome
		int[] P = new int[S.length()];

		// P[i] contains the length of longest palindrome (in S not original in) centered at i

		for(int i=0;i<P.length(); i++) 
			P[i] = 0;
		// for each position find longest palindrome centered at the position, save length in P

		for(int i=0; i<S.length; i++){
			int i_mirror = 2*C-i; // as C - i_mirror = i - C due to symmetric property 
		
			/*When R-i > P[i_mirror] then palindrome at center i_prime contained completely within palindrome centered at C.  Otherwise R-i <= P[i_mirror] means that the palindrome at ceter i_mirror  doesn’t fully contained in the palindrome centered at C. In this case palindrome at i is extendable past R*/

			P[i] = (R>i) ? min(P[i_mirror], R-i) : 0;

			// if palindrome centered at i is extendable past R then extend R to the right edge of newly extended palindrome

			while(S[i+P[i]+1] == S[i-P[i]-1])
				P[i]++;

			// If palindrome centered at i extend past R then update Center to i

			if(i+P[i] > R){
				C = i;
				R = i+P[i];
			}
		}
		return extractLongest(in, P);
	}

	public int extractLongest(String in, int[] P){
		int longestCenter = 0;
		int longestLength = 0;

		for(int i=0; i<P.length; i++){
			if(P[i] > longestLength){
				longestLongest = P[i];
				longestCenter = i;
			}
		}

		return in.substring((longestCenter-longestLength-1)/2, longestLemgth);
	}

	public Set<String> allPalindromicSubstring(String in, int[] P){
		HashSet<String> all = new HashSet<String>();

		for(int i=0; i<P.length;  i++){
			if(P[i] != 0)
				all.add(in.substring((i-P[i]-1)/2, P[i]));
		}	

		return all;
	}
}

public class NumberOfPalindromes {

	private void countPalindromes(String s) {
		boolean[][] palindromes = buildPalindromeTable(s);
		int count = 0;
		
		for (int i = 0; i < palindromes.length; i++) {
			for (int j = 0; j < palindromes[0].length; j++) {
				if (palindromes[i][j] == true) {
					count++;
				}
			}
		}

		System.out.println(count);
	}

	private boolean[][] buildPalindromeTable(String s) {
		boolean[][] lookUpTable = new boolean[s.length()][s.length()];
		for (int i = 0; i < s.length(); ++i)
			lookUpTable[i][i] = true;
		for (int i = 1; i < s.length(); ++i) {
			int left = i - 1, right = i;
			while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
				lookUpTable[left--][right++] = true;
			}
			left = i - 1;
			right = i + 1;
			while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
				lookUpTable[left--][right++] = true;
			}
		}
		return lookUpTable;
	}

	public static void main(String[] args) {
		NumberOfPalindromes palindromes = new NumberOfPalindromes();
		palindromes.countPalindromes("abba");
	}
}

Modify Manacher's in the obvious way.

(i.e.,  array of struct { int length_longest_centred_here; int num_centred_here; } ).
                                  ^^^^^^^^                           ^^^^^
                                 part of Manac.                   added for this quest

Should work without added complexity in big-O
Haven't checked though.

Modify Manacher's in the obvious way.

(i.e.,  array of struct { int length_longest_centred_here; int num_centred_here; } ).
                                  ^^^^^^^^                           ^^^^^
                                 part of Manac.                   added for this quest

Should work without added complexity in big-O
Haven't checked though.

Complexity: O(N^2)
Explanation: Look for odd length palindromes centered at i, look at even length palindromes starting with i as the left character.
Note: not sure why formatting is off.


//O(N^2) implementation

int numPallindromes3(String s) {

int numPallindromesCounter = 0;

for (int i = 0; i < s.length(); i++) {

for (int j = 1; j < s.length()/2; j++) {

if (i - j < 0 || i + j >= s.length()) continue;

String odd1 = s.substring(i-j, i-j+1);
String odd2 = s.substring(i+j, i+j+1);

if (odd1.equals(odd2)) {
numPallindromesCounter++;
System.out.println(s.substring(i-j,i+j+1));
} else
break;

}

for (int k = 1; k < s.length()/2 + 1; k++) {

if (i - k + 1< 0 || i + k >= s.length()) continue;
String even1 = s.substring(i-k+1, i-k+2);
String even2 = s.substring(i+k, i+k+1);

if (even1.equals(even2)) {
numPallindromesCounter++;
System.out.println(s.substring(i-k+1,i+k+1));
} else
break;

}

}


return numPallindromesCounter;
}

public static int findNumOfPalindromes(String s) {
//        Find number of palindromes in a string
        if (s == null || s.isEmpty()) {
            return 0;
        } else if (s.length() == 1) {
            return 1;
        } else {
            int res = s.length();
            for (int i = 0; i < s.length() - 1; i++) {
                boolean broke = false;
                int dif = 1;
                while (!broke && i - dif >= 0 && i + dif < s.length()) {
                        if (s.charAt(i - dif) == s.charAt(i + dif)) {
                            res++;
                        } else {
                            broke = true;
                        }
                        dif++;
                }
                if (s.charAt(i) == s.charAt(i + 1)) {
                    dif = 1;
                    broke = false;
                    res++;
                    while (!broke && i - dif >= 0 && i + 1 + dif < s.length()) {
                            if (s.charAt(i - dif) == s.charAt(i + 1 + dif)) {
                                res++;
                            } else {
                                broke = true;
                            }
                        dif++;
                    }
                }
            }
            return res;
        }
    }

TIme Complexity O(n2)

public class NumberofPalindromesInString {
	String str = "";
	NumberofPalindromesInString(String str){
		this.str = str;
	}
	
	public void NumberofPalindromesInString(){
		if(str == null || str.length() == 0){
			System.out.println("Number of Plaindromes "+0);
			return;
		}
		
		int len = str.length(), i =0, j=0;
		
		
		boolean[][] s = new boolean[len][len];
		
		for(i =len-1; i >= 0; i--){
			for(j = i; j< len;j++){
				if( i == j){
					s[i][j] = true;
				} else if( j == i+1){
					s[i][j] = (str.charAt(i) == str.charAt(j));
				} else{
					s[i][j] = s[i+1][j-1] && (str.charAt(i) == str.charAt(j));
				}
			}
		}
		int count = 0;
		
		for(i = 0; i< len; i++){
			int k = i;
			for(j =i; j< len;j++){
				if(s[i][j] && j > k)
					k = j;
			}
			count++;
			i = k+1;
		}
		
		System.out.println("Number of Plaindromes "+count);
	}
	
}

//Get each word from string and then call another method to know if it is palindrom or not. if it is then increase the count
//Space complexity is O(1) & Processing will be O(M+K) where m is the number of word and k will be number of character.

public int FindNumberOfPalindrom(string s)
        {      
            int _palindromCount = 0;
            string[] words = s.Split(' ');

            foreach (string word in words)
            {
                if (IsPalindrom(word))
                    _palindromCount++;
            }

            return _palindromCount;

        }

        public bool IsPalindrom(string word)
        {
            bool isPalindrom = true;
            for (int i = 0, j = word.Length - 1; i <= word.Length/2; i++, j--)
            {
                if (word[i] != word[j])
                    isPalindrom = false;
            }

            return isPalindrom;
        }

O(n^2) algorithm

/*
 * CountingPalindromes.cpp
 *
 *  Created on: Nov 2, 2013
 *
 */

/*
 * Find number of palindromes in a string
 */

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;


vector<string> countPalindromes(string s){
	vector<string> palindromes;
	char * letters = new char[s.length() + 1];
	strcpy(letters,s.c_str());
	int j,k;
	int i = 0;
	for(i = 0;i < s.length();i++){
		j = i - 1;
		k = i + 1;
		while(j >= 0 && k < s.length() && letters[j] == letters[k]){
			palindromes.push_back(s.substr(j,k - j + 1));
			j--;
			k++;
		}
	}
	for(i = 1;i < s.length();i++){
		j = i - 1;
		k = i;
		while(j >= 0 && k < s.length() && letters[j] == letters[k]){
			palindromes.push_back(s.substr(j,k - j + 1));
			j--;
			k++;
		}
	}
	return palindromes;
}

int main(){
	string s;
	cout << "Enter a string:" << endl;
	getline(cin,s);
	cout << "you entered:" << s << endl;
	vector<string> palindromes = countPalindromes(s);
	cout << "Number of palindromes in the given string " << s << ":" << palindromes.size() << endl;
	cout << "The palindromes found are:" << endl;
	vector<string>::iterator itr;
	for(itr = palindromes.begin();itr != palindromes.end();itr++)
		cout << *itr << endl;
	return 0;
}

#include <stdio.h>
#include <string.h>

int is_parlindromes( char * str, int str_len)
{
int len = str_len;
int i = 0;

for ( i = 0; i < len/2; i ++)
{
if (str[i] == str[len - i - 1])
continue;
else
return 0;
}

return 1;
}

void print_parlindromes (char *str, int len)
{
int i = 0;
for (i = 0; i < len; i ++)
{
printf("%c", *(str+i));
}
printf ("\n");
}

int main (int argc, char *argv[])
{
int num_of_parl = 0;
int i = 0;
int len = 0;
char *pStr = argv[1];

if (argc != 2)
{
printf ("Need Parameter string!\n");
return 1;

}

printf ("Input string:\n%s\n\n", pStr);

len = strlen (pStr);

printf ("Parlindromes:\n");

for (i = 0; i < len; i ++)
{
int j = 0;
int sub_str_len = strlen(pStr + i);

for (j = 2; j <= sub_str_len; j ++)
{
if (is_parlindromes (pStr + i, j))
{
print_parlindromes (pStr + i, j);

num_of_parl ++;
}
}
}

printf ("\nNumber of parlindromes:%d\n", num_of_parl );

return 0;
}
--------------------------
The result of testing.

./parlindromes abcdefedcdef
Input string:
abcdefedcdef

Parlindromes:
cdefedc
defed
efe
fedcdef
edcde
dcd

Number of parlindromes:6

{{
#include <stdio.h>
#include <string.h>

int is_palindromes( char * str, int str_len)
{
int len = str_len;
int i = 0;

for ( i = 0; i < len/2; i ++)
{
if (str[i] == str[len - i - 1])
continue;
else
return 0;
}

return 1;
}

void print_palindromes (char *str, int len)
{
int i = 0;
for (i = 0; i < len; i ++)
{
printf("%c", *(str+i));
}
printf ("\n");
}

int main (int argc, char *argv[])
{
int num_of_parl = 0;
int i = 0;
int len = 0;
char *pStr = argv[1];

if (argc != 2)
{
printf ("Need Parameter string!\n");
return 1;

}

printf ("Input string:\n%s\n\n", pStr);

len = strlen (pStr);

printf ("Parlindromes:\n");

for (i = 0; i < len; i ++)
{
int j = 0;
int sub_str_len = strlen(pStr + i);

for (j = 2; j <= sub_str_len; j ++)
{
if (is_palindromes (pStr + i, j))
{
print_palindromes (pStr + i, j);

num_of_parl ++;
}
}
}

printf ("\nNumber of palindromes:%d\n", num_of_parl );

return 0;
}

}}

--------------------------
The result of testing.

./parlindromes abcdefedcdef
Input string:
abcdefedcdef

Parlindromes:
cdefedc
defed
efe
fedcdef
edcde
dcd

Number of parlindromes:6