CareerCup

Here is O(N^2) solution.
1. Count all even length palindromes.
2. Count all odd length palindromes.
3.return count.

int countPalindrome(char *str)
{
	int i,j,k,count=0;
	for(i=0;str[i];i++)
	{
		k=i-1;j=i+1;  //count odd length palindromes
		while(k>=0 && str[j] && str[k]==str[j])
		{
			++count;
			k--;j++;
		}

		k=i;j=i+1; //count even length palindrome
		while(k>=0 && str[j] && str[k]==str[j])
		{
			++count;
			k--;j++;
		}
	}
	return count;
}

Can someone post the implementation of suffix array?

codes-to-problem.blogspot.in/

Create a suffix tree of the word and also the word formed by reversing the word. Then simply count all the suffixes that occur in both tree that are palindromes.

I have tried it with O(n^2) the best I could get..

#include <stdio.h

/*
 * 
 */
void main()
{
    char test[] = "xzyabcbaty";
    //first check where the possible palindrom exists
    int i, counter=0, j;
    int start[10], end[10], possible_candidates=0;
    for ( i=0 ; i<sizeof(test)-1 ; i++)
    {
        for (j=i+1 ; j < sizeof(test) ; j++)
        {
            if (test[i] == test[j])
            {
                start[counter] = i;
                end[counter] = j;
                possible_candidates++;
                counter++;
            }
        }
    }


    //check if we have any possibility of palindrom
    if (counter)
    {
        int num_of_substring = 0;
        for (i=0 ; i < possible_candidates ; i++)
        {
            if (is_palindrom(test, start[i], end[i]))
            {
                num_of_substring++;
            }
        }
        printf("Total number of substrings %d", num_of_substring);
    }
    else
    {
        printf("Nothing found");
    }
}

/*
 * palidrom checking function with O(n/2)
 */
int is_palindrom(char* string, int start, int end)
{
    int i, j=0;
    for (i=start ; i < end ; i++)
    {
        if (string[i] != string[end-j])
        {
            return 0;
        }
        j++;
    }
    return 1;
}

The complexity is O(n^2) + O(n^2) which is 2(O(n^2) => O(n^2)

Follow the below steps:
1. Reverse the string and add it to the original string. For eg if the string given is 'banana' take is as 'banana#ananab'
2. Make a suffix array of this string.
3. Put all the suffixes in a hashmap and sort the hashmap to avoid duplicate entries, you can even use arrays.
4. Now find the common prefix in the adjacent strings. Iterate through the hasmap or array created in last point. If you want youcan store this common prefix in a seperate array p. The array p contains all the palindrome string. You can count all the palindrome greater than any length or the longest palindrome.

My idea is to use DP.

s[i,j]= 1 if s[i+1,j-1]=1 && A[i]=A[j], where i+1<=j-1
if A[i]=A[i+1] if i=j-1
0 otherwise

sum=0;
for(i=n; i>=0;i--)
{
for(j>=n;j>=i;j--)
{
if(i==j)
S[i,j]=1;
else
{
if(j=i+1)
{
if(A[i]==A[j])
s[i,j]=1;
else
s[i,j]=0;
}
else
{
if(s[i+1,j-1]==1 && A[i]==A[j])
s[i,j]=1;
else
s[i,j]=0;
}
}
sum += s[i,j];
}
}

#include<stdio.h>
int checkpalindrom(char *s,char *s1)
{
while(s<s1)
if(*s++!=*s1--)
return 0;
return 1;
}

void main()
{
char string[30],c;
int i=0,j=0,n=0;

printf("\n Enter the Msg :- ");
gets(string);

printf("\n Palindram substring are as follow \n\n");

for(i=0,j=0;string[i];i++)
{
if(string[i]==' ' || string[i]=='\t')

{ c=*(string+i);

*(string+i)='\0';

if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);

*(string+i)=c;

j=i+1;
}

}

if(checkpalindrom(string+j,string+i-1))
printf("\n %d) %s",++n,string+j);

}
input and output as follow ....


Enter the Msg :- hi madam and mom gud day

Palindram substring are as follow

1) madam
2) mom

#include "stdio.h"
#include "string.h"

int main() {
    char * str = "abababbaa";
    printf("hello world from panindrom!\n");
    printf("%s has %d panindrom\n",str, getNumberOfPanindrom(str));
}

int getNumberOfPanindrom(char * str) {
    return center_in_even_position(str) + center_in_odd_position(str);
}

int center_in_odd_position(char * str) {
    int i,j = 0;
    int count = 0;
    int size = strlen(str);
        for( i = 0; i < size; i++)
        {
            for( j = 1; j <= min(i, size - i - 1); j++)
            {
                if(str[i-j] == str[i+j])
                    count ++;
                else
                    break;
            }
        }
    return count;
}

int center_in_even_position(char * str) {
    int i, j = 0;
    int count = 0;
    int size = strlen(str);
        for( i = 0; i < size; i ++)
        {
            for (j = 0; j < size - i - 1; j++)
            {
                if(str[i-j] == str[i+j+1])
                    count ++;
                else
                    break;
            }
        }
    return count;
}

int min(int a, int b) {
    return ((a > b) ? b : a);
}

This solution works in O(n+p) where n is the length of string and p is the length of palindrom patterns. In worst case it would be O(n^2)
check it:

/a.out "baab check aa abc zxz it adda hhh "
./a.out " baab check aa abc zxz it adda hhh "
./a.out

#include <iostream>
using namespace std;

int palindromesCount(char *input)
{
    int countpalindromes=0;
    int wordStart=0,wordEnd=0;
    int charStart,charEnd;
    while(input[wordStart] != '\0') {
        if(input[wordStart] != ' ') {
            for(wordEnd = wordStart; input[wordEnd] != ' ' & input[wordEnd] != '\0'; wordEnd++); wordEnd--;
            charStart = wordStart;
            charEnd = wordEnd;
            while( ((charEnd-charStart) > 0) & (input[charEnd]==input[charStart]) ) { charStart++; charEnd--;};
            if( (charEnd-charStart) <=0 ) countpalindromes ++;
            wordStart = wordEnd+1;                      
        }   
        else wordStart++;   
    }   
    return countpalindromes;
};

main(int argc, char *argv[])
{
    if(argc>1) cout << palindromesCount(argv[1]) << endl;
}

you can use a suffix array to get a O(nlogn) algorithm
first construct a new string S+'#'+S' which # is not in char set of S and S' is the reversion of S. Then build a suffix array and calculate the longest common prefix.
sum up each i < len(S) , LCP(Rank[i],Rank[2n-i]) you got the final answer.
if the LCP use a segment tree then each query take O(lgn) time. so the total complexity of the algorithm is O(nlogn)

Calculate polinomial hash function for each prefix with O(n) complexity. Next we can calculate hash for some substring in O(1). Next fix center and parity of length and iterate length using binary search to find longest palindrome with fixed center. So we will get O(n log n) complexity.

int countPalindromes(const string& str)
        {
                  int N = str.size();
                  vector< vector<int> > dp(N, vector<int>(N, 0));
                  int cnt = 0;
                  for (int i=0; i < N; i++)  {
                             cnt += (dp[i][i] = 1);
                   }
                   for (int k=1; k < N; k++)
                             for (int j=k, i=0; j < N; j++, i++)
                                        cnt += (dp[i][j] = str[i] == str[j] & dp[i+1][j-1];
                   return cnt;
        }

#include<bits/stdc++.h>
using namespace std;

int main()
{
string s;
cin>>s;
int sz = s.length();
int count=0;
for(int i=0;i<sz;i++) {
for(int j=i;j<sz;j++)
{
string t = s.substr(i,j-i+1);
string rev = t;
reverse(rev.begin(),rev.end());
if(rev==t)
count++;
}
}
cout<<count<<endl;
}

{
#include<bits/stdc++.h>
using namespace std;

int main()
{
string s;
cin>>s;
int sz = s.length();
int count=0;
for(int i=0;i<sz;i++) {
for(int j=i;j<sz;j++)
{
string t = s.substr(i,j-i+1);
string rev = t;
reverse(rev.begin(),rev.end());
if(rev==t)
count++;
}
}
cout<<count<<endl;
}
}

/*
About Program: Finding all the possible substrings of a given string as well as finding the palindrome substrings in it.
Date: 19/07/2012
Author: Aditya Dhaniwala
*/
#include<stdio.h>
#include<conio.h>
#include<string.h>
main()
{
int i,j,k,flag=0,c=0,num=0,num2=0;
char str[200],strcopy[200]={"\0"},stringconcat[200]={"\0"},temp[2]={"\0"},temp2[2]={"\0"};
printf("Enter the string : ");
gets(str);
for(i=0;i<strlen(str)-1;i++)
{
temp[0]=str[i];
strcat(stringconcat,temp);
for(j=i+1;j<strlen(str);j++)
{
temp2[0]=str[j];
strcat(stringconcat,temp2);
printf("%s\n",stringconcat);
num2++;
strcpy(strcopy,stringconcat);
strrev(strcopy);
flag=strcmp(stringconcat,strcopy);
if(flag==0)
{
printf("Palindrome string = %s\n",strcopy);
c=1;
num++;
}
}
for(k=0;k<200;k++)
{
stringconcat[k]='\0';
strcopy[k]='\0';
}
}
if(c==0)
printf("CANNOT FIND A PALINDROME SUBSTRING");
printf("\nTotal number of palindromes of the main string and its substring = %d\nTotal number of substrings possible=%d",num,num2);
getch();
}

using dynamic programming.

int Dp(std::string & str) {
  int n = str.size();
  std::vector<std::vector<int> > dp(n, std::vector<int>(n, 0));
  int rs = 0;
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n - k; i++) {
      if (k == 0) dp[i][i + k] = 1;
      else if (k == 1) dp[i][i + k] = str[i] == str[i + k] ? 1 : 0;
      else {
        if (dp[i + 1][i + k - 1] && str[i] == str[i + k]) dp[i][i + k] = 1;
      }
      if (dp[i][i + k] == 1) rs++;
    }
  }
  return rs;
}

O(n^2) algo:

require 'pp'

str = "and";
res = []
count = 0

pp str.length
(0..(str.length-1)).each{|i|
	res[i] = []
	(0..(str.length-1)).each{|j|
		if i>j
			res[i][j] = -1
		elsif i == j
			res[i][j] = 1
			count += 1
		else
			if ((res[i][j-1] == 1) and (str[j] == str[i]))
				res[i][j] = 1
				count += 1
			else
				res[i][j] = 0
			end
		end
	}
}

pp res
pp count

if(a[i][j]&&str[i-1]==str[j+1])
a[i-1][j+1]=1

does it work? but i think the time is O(n^2)...

tag. O(n) solution is not intuitive.

Here is my O(n) solution. The code uses extra storage to track the number of characters matched at the current position based on the number of characters matched at the previous position. The matching logic simply compares the current position to the even & odd offsets based on the number of matches seen in each case previously. The insights I had were
1. It seemed very similar to the KMP substring problem
2. Each palindrome of length n had n/2 smaller palindromes
3. Once characters start matching, the palindrome will continue to expand until it stops at which point a new palindrome starts from that index

Please comment if you find bugs.

Thanks

#define array_elements(_a) (sizeof((_a)) / sizeof((_a)[0]))

#define MAX_LENGTH 4096

#define PRINT_PALINDROME_SUBSTRINGS 1

void
print_palindrome_substring(
    char *s, int start, int end, char *message, int count
    )
{
    printf("%s [%d]: ", message, count);

    while (start <= end) {
        printf("%c", s[start]);
        start++;
    }

    printf(".\n");
}


int
count_palindrome_substrings(
    char *s
    )
{
    int pred_even[MAX_LENGTH];
    int pred_odd[MAX_LENGTH];
    int i;
    int count;
    int off;

    pred_even[0] = 0;
    pred_odd[0] = 0;
    i = 1;
    count = 0;

    while (s[i] != 0) {
        off = i - 1 - 2 * pred_even[i - 1];

        if (off >= 0 && s[off] == s[i]) {
            pred_even[i] = pred_even[i - 1] + 1;
            count++;

#if PRINT_PALINDROME_SUBSTRINGS
            print_palindrome_substring(s, off, i, "even", count - 1);
#endif // PRINT_PALINDROME_SUBSTRINGS

        } else {
            pred_even[i] = 0;
        }

        off = i - 1 - 2 * pred_odd[i - 1] - 1;
        if (off >= 0 && s[off] == s[i]) {
            pred_odd[i] = pred_odd[i - 1] + 1;
            count++;

#if PRINT_PALINDROME_SUBSTRINGS
            print_palindrome_substring(s, off, i, "odd", count - 1);
#endif // PRINT_PALINDROME_SUBSTRINGS

        } else {
            pred_odd[i] = 0;
        }

        i++;
    }

    return count;
}


int
main(
    int argc,
    char **argv
    )
{
    int i;
    char *palindrome_substrings_test[] = {
        "abbba",
        "abbabcddcbaefghihgfe" };

    for (i = 0; i < array_elements(palindrome_substrings_test); i++) {

        printf(
            "count_palindrome_substrings(%s) = %d.\n",
            palindrome_substrings_test[i],
            count_palindrome_substrings(palindrome_substrings_test[i]));
    }
}

int palidrome_count(const char *a, int n)
{
int i;
int len;
int count = n;

int **p = (int **)malloc(sizeof(int *) * n);
for (i = 0; i < n; ++i) {
p[i] = (int *)malloc(sizeof(int) * (n+1));
memset(p[i], 0, sizeof(int) * (n+1));
p[i][0] = p[i][1] = 1;
}

for (len = 2; len <= n; ++len) {
for (i = 0; i + len < n; ++i) {
p[i][len] = ((a[i] == a[i + len - 1]) ? 1 : 0) & p[i+1][len-2];
count += p[i][len];
}
}

for (i = 0; i < n; ++i) {
free(p[i]);
}
free(p);

return count;
}

I think Manacher algo can solve this in O(n), I implement two algos:
1. longestPalindrome is O(n) using Manacher
2. partition is O(n^2) using 2-order DP

#include <stdio.h>
#include <iostream>
#include "climits"
#include "vector"
#include "cstring"
#include <sstream>
#include "cstdlib"
#include "map"
#include "algorithm"
#include "cmath"
#include "queue"
#include "stack"

using namespace std;

class Solution {
public:
    int longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stringstream ss;
        int n = s.size();
        ss << "#";
        for(int i = 0; i < n; i++){
            ss << s[i] << "#";
        }
        string ns = ss.str();

        int ret = 0;

        vector<int> arr(ns.size(), 0);
        int cm = 0;
        int ci = 0;
        for(int i = 0; i < ns.size(); i++){
            int pi = 2 * ci - i;
            int pl = 0;
            if(pi >= 0){
                pl = arr[pi];
            }
            if(i + pl < cm){
                arr[i] = pl;
            }else{
                while(i + pl < ns.size() && i - pl >= 0){
                    if(ns[i + pl] != ns[i - pl]) break;
                    else pl++;
                }
                pl -= 1;
                arr[i] = pl;
                if(pl > cm) cm = pl;
            }
            ret += (arr[i] + 1) / 2;
        }

        return ret;
    }

    int partition(string s) {
        int n =  s.size();
        vector< vector< bool > > palindromeMatrix(n, vector<bool>(n, false));
        for (int i = 0; i < n; i++) {
            palindromeMatrix[i][i] = true;
        }
        int ret = n;
        for (int margin = 1; margin < n; margin++) {
            for (int i = 0; i < n - margin; i++) {
                int j = i + margin;
                if ((i + 1 > j - 1 || palindromeMatrix[i + 1][j - 1])
                        && s[i] == s[j]) {
                    palindromeMatrix[i][j] = true;
                    palindromeMatrix[j][i] = true;
                    ret += 1;
                }
            }
        }
        return ret;
    }
  
};


int main(int argc, char** argv) {
    Solution ss;
    string s = "abaaba";
    cout << ss.longestPalindrome(s) << endl;
    cout << ss.partition(s) << endl;
}

This can be done in O(n) and i did this in O(n) in college. Now i cant remember this. If anyone knows please let me know.

Use a stack. Perform one linear pass through the string, compare current element to the one on top of the stack. If they're the same, pop the element and increment the counter. If not, clear the contents of the stack and push current element onto stack.

EDIT: sorry this is wrong.

# include <stdio.h>
void main()
{
string s1[10],s2[10];
strcpy(s1,s2);
s2= strrev(s2);
if(strcmp(s1=s2))
{
printf("it is plaindrome");
else
printf("it is not a palindrome");
}