CareerCup

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/#demoForm
explains an elegant solution.

The answer I gave there was not even close (I checked it later after the interview).. got a reject

is there a way u can explain that .. i couldnt understand that stuff ? :(

Hi all,

here is code in C:

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

int main(){
int len,i,j=0,index,tempindex,count,tempcount;
char str[100],*ptr;
printf("\nEnter String: ");
scanf("%s",str);
len=strlen(str);
ptr=str;
index=0;
count=0;


//finding longest palindrome of odd length
for(i=1;i<len-1;i++){
j=1;
while(((i-j) >= 0) && ((i+j) < len) && (str[i-j]==str[i+j]))
			j++;

if(j-1>count){
				index=i;
				count=j-1;
			}	
}


if(count>=1){
					index=index-count;
 					count=2*count+1;
					}


//finding longest palindrome of even  length
tempcount=0;
tempindex=0;
for(i=0;i<len-1;i++){
j=0;
while(((i-j) >= 0) && ((i+j+1) < len) && (str[i-j]==str[i+j+1]))
			j++;

if(j>tempcount){
				tempindex=i;
				tempcount=j;
			}	
}


if(tempcount>0)
	{
	tempindex=tempindex-tempcount+1;
	tempcount=tempcount*2;
	}

//if even palindrome's length is greater than odd palindrome's length 
if(tempcount>count)
	{
	index=tempindex;
	count=tempcount;
	}

printf("\nindex=%d, count= %d",index,count);


if(count==0)
	printf("\nNo Palindrome");
else{
	ptr=ptr+index;
	ptr[count]=NULL;
  printf("\nLongest Palindrome: %s",ptr);
}

}

I guess the tree thing is better..

reverse the given string and do the longest common subsequence routine between the string and the reveresed string.....

that program didnt work when i tested it with a very long sequence

gotcha, I just tried it really quickly last night before bed, I didn't really feel like trying to figure out why it didnt work.

#include<stdio.h>

int main(){

  char st[100];
	int index=0;
	int max=-1;
	int offset=0;
	int midindx=0;

// Input

printf("\nEnter String:");
scanf("%s",st);

//max palindrome of odd length
	while(st[index+offset] != NULL){
				offset=0;
				while((index >= offset) && (st[index + offset] != NULL ) && (st[index + offset] == st[index - offset])){
								if(offset>max){
									max = offset;
									midindx=index;
								}
								
							offset++;
				}
				index++;			
	}	
		
	
	if(max != -1){
		printf("\nMax Odd length palindrome of length %d is : %.*s\n",2 * max +1,2 * max +1, &st[midindx-max]);
	}

//max palindrome of even length

	int index1=0;
	int max1=-1;
	int offset1=0;
	int midindx1=0;
	
	while((st[index1 + offset1] != NULL) && (st[index1 + offset1 + 1] != NULL)){
				offset1=0;
				while((st[index1 + offset1 + 1] != NULL) && (index1 >= offset1) && (st[index1 - offset1] == (st[index1 + offset1 + 1] ))){
							if(offset1 > max1){
								max1 = offset1;
								midindx1 = index1;
							}
							offset1++;
				}
				index1++;
	}			

	if(max1 != -1){
		printf("\nMax Even length palindrome of length %d is : %.*s\n",2 * max1 + 2,2 * max1 + 2, &st[midindx1-max1]);
	}
}

i have gone through this question ..my solution is based on this matrix view

X M A D A M Y X
X 1 0 0 0 0 0 0 1
M 0 1 0 0 0 1 0 0
A 0 0 1 0 1 0 0 0
D 0 0 0 1 0 0 0 0
A 0 0 1 0 1 0 0 0
M 0 1 0 0 0 1 0 0
Y 0 0 0 0 0 0 1 0
X 1 0 0 0 0 0 0 1

we have created this matrix putting 0 when characters in row and column are different and 1 when equal. its easy to see that all the palindromes will lie around the main diagonal (in the direction of second diagonal). in this way we can find out all the palindromes in the given string and of course the palindrome with maximum length.

only problem is the space.

#include <stdio.h>
#include <stdlib.h>


int palindrome(char* s, int p, int r)
{
  int x1, x2;

  if (p == r) {
    return 1;
  }
  else if (p > r)
    return 0;
  else {
    if (s[p] == s[r]) {
      return 2 + palindrome(s,p+1,r-1);      
    }
    else {
      x1 = palindrome(s,p,r-1);
      x2 = palindrome(s,p+1,r);
      return (x1 > x2) ? x1 : x2;
    }
  }
}

int main(int argc, char* argv[])
{
  char s[80];

  printf("Enter a string\n");
  scanf("%s",s);

  printf("Longest length is %d\n",palindrome(s,0,strlen(s)-1));
}

can we write a subroutine that tests for a palindrome and then check substrings with end characters deleted from the original string? i'm guessing this is a O(n^3) algorithm.

#include <iostream>
#include <string>

using namespace std;

int main()
{
string str;
string palindrome;
cin >> str;
for(int i=1; i <= str.length()-2; ++i)
{
int temp = 1;
while(((i-temp) >= 0) && ((i+temp) <= str.length()-1) && (str[i-temp] == str[i+temp]))
++temp;
if(temp > 1)
{
string newPalindrome = str.substr(i-(temp-1), 2*(temp-1)+1);
if(newPalindrome.length() > palindrome.length())
palindrome = newPalindrome;
}
}

cout << endl << palindrome;

}

Why dont you guys include comments along with the code? It will be so much helpful.

Hmm... I was recently asked to develop an algorithm that counts the number of palindromes in a string (excluding palindromes inside other palidromes). Below is the c# code I turned in. Can anyone let me know if it works or if it contains a bug, etc. I decided to google palindromes after I already turned in my code, which is how I found this site. Thanks.


using System;

namespace PalindromeCount
{
class Program
{
static void Main(string[] args)
{
bool terminate = false;

do
{
Console.WriteLine("\nEnter input string below:");
string inputString = Console.ReadLine();

string palindromes = "";
int Count = GetPalindromeCount(inputString,
ref palindromes);

string output = "\nPalindrome count: ";
output += Count.ToString();
output += "\nPalindromes: ";
output += palindromes;
Console.WriteLine(output);


Console.WriteLine("\nTerminate (Y/N):");
string input = Console.ReadLine();

if (string.Compare(input, "Y", true) == 0)
{
terminate = true;
}

} while (terminate == false);
}

//This method returns the number palindromes
//within the input string
//it stores the palindromes found in
//the palindromes argument
public static int GetPalindromeCount(string str,
ref string palindromes)
{
palindromes = "";
int lastEndIndex = 0;
return GetPalindromeCount(str,
0,
str.Length - 1,
ref lastEndIndex,
ref palindromes);
}

//This is a recursive method that counts
//the number of palindromes
//within a subset (substring) of the input string
//between the startindex and endindex

//if the entire substring is not a palindrome, this method
//looks for the next palindrome by searching for the longest
//leftmost palindrome of the substring. This is done by
//reducing the end index by 1 until a palindrome is found.
//However, the endindex cannot be reduced beyond the
//end index (lastEndIndex) of the last leftmost
//palindrome found. This ensures that smaller
//palindromes within larger leftmost palindromes are not
//counted

//Upon searching for the longest leftmost palindrome,
//this method then calls it self again with a substring
//that is one chararcter less to the left of the input
//substring. Again, by using the lastEndIndex as a limit
//smaller palindromes within previously found leftmost
//palindromes are avoided

private static int GetPalindromeCount(string str,
int startIndex,
int endIndex,
ref int lastEndIndex,
ref string palindromes)
{
//The length of the substring must be greater than 1
//because the length of palidromes must be 2 or more

//The endindex is reduced during recursion, however,
//the endindex must be greater than the lastendindex
//to prevent smaller leftmost palidromes within longer
//leftmost palindromes
if (startIndex >= endIndex || lastEndIndex >= endIndex)
{
return 0;
}

//return 1 and exit, if the entire substring is a
//palindrome
else if (IsPalindrome(str, startIndex, endIndex))
{
//add the newly found palidrome to the list
//of palindromes
palindromes += str.Substring(startIndex,
endIndex - startIndex + 1)
+ " ";
return 1;
}


else
{
int Count = 0;

//get the longest leftmost palindrome
//of the substring found
string left = GetLeftmostPalindrome(str,
startIndex,
endIndex - 1,
lastEndIndex);
if (left.Length > 1)
{
//set the last leftmost last index found
lastEndIndex = startIndex + left.Length - 1;
Count = 1;

//add the newly found palidrome to the list
//of palindromes
palindromes += left + " ";
}

//search for other palidromes but avoid those within
//previously found leftmost palidromes
//by using lastEndIndex
return GetPalindromeCount(str,
startIndex + 1,
endIndex,
ref lastEndIndex,
ref palindromes)
+ Count;
}
}

//This method returns the longest leftmost palidrome
//of the substring, if found
//or an empty string
private static string GetLeftmostPalindrome(string str,
int startIndex,
int endIndex,
int lastEndIndex)
{
//The length of the substring must be greater than 1
//because the length of palidromes must be 2 or more

//The endindex is reduced during recursion, however,
//the endindex must be greater than the lastendindex
//to prevent smaller leftmost palidromes within longer
//leftmost palindromes
if (startIndex >= endIndex || lastEndIndex >= endIndex)
{
return "";
}

//return 1 and exit, if the entire substring is a
//palindrome
else if (IsPalindrome(str, startIndex, endIndex))
{
return str.Substring(startIndex,
endIndex - startIndex + 1);
}

//reduce the substring by 1 character to the right
//and try again
else
{
return GetLeftmostPalindrome(str,
startIndex,
endIndex - 1,
lastEndIndex);
}
}

//return true if the substring is a palindrome
private static bool IsPalindrome(string str,
int startIndex,
int endIndex)
{
//The length of the substring must be greater than 1
//because the length of palidromes must be 2 or more
if (startIndex >= endIndex)
{
return false;
}

int left = startIndex;
int right = endIndex;
char[] strChars = str.ToCharArray();

do
{
if (strChars[left] != strChars[right])
{
return false;
}

left++;
right--;

} while (left < right);

return true;
}
}
}

Why all the trouble of trees and things. Reverse the string and then find the intersection of the string and the reversed string.

Ozzy, think again.

for OZZy:
Your solution is correct, but not efficient. It takes O(n^2) time to find the intersection of the string and the reversed string (since it is not sorted number and you can not sort them).

In stead, we can create two suffix arrays(or suffix trees) for string and reversed string respectively, and then easily get the longest common character of hneighbor elements.

Why would it take O(n^2) in Ozzy's case? I think it would be O(n).

Why would it take O(n^2) in Ozzy's case? I think it would be O(n).

Why would it take O(n^2) in Ozzy's case? I think it would be O(n).

Here is fully working code:

void DetectPalindrome(char *str){
int j=0;
int len=1;
int sz=(int)strlen(str);

//find the center point of the palindrome
for(int i=j+1;i<sz;i++){
if(str[i-1]==str[i+1]){
j=i;
//find the length of palindrome
while((j-len-1>=0) && (j+len+1<sz) && str[j-len-1]==str[j+len+1])len++;

//print
for(int k=j-len;k<=j+len;k++)
cout<<str[k];
cout<<endl;
len=1;
}
}
}