# longest palindromic substring

*Longest palindrome sub-string problem is famous for software programmers specially for interview purpose. you can be questioned to write a function that returns the longest palindrome in a given string. A palindrome is a sequence which reads the same backward or forward. For example “asantaatnasa” is sequence of character which reads same in backward or forward. in simple term if we reverse the sequence we will get same sequence.*

*Longest palindrome sub-string problem*: *For example, the longest palindromic sub-string of “bananas” is “anana” and length is 5.*

*Simple solution with O(N²) time complexity*

*The give string is “***bananas**“.*if we reverse the given sequence then we will get “***sananab**“.*Then our problem is to find longest common sub-string between these two strings “***bananas**” and*“***sananab**“.*The longest common sub-string problem can be solved by recursive function with memoization with O(m*n) time complexity discussed in the article http://wikistack.com/longest-common-substring-problem/**Hence**Longest common sub-string solution can be used to compute**Longest palindrome sub-string problem with**O(m*n) time complexity.*

* Here is c code for Longest common sub-string solution with O(m*n) time complexity.*

#include<stdio.h> #include<stdbool.h> #include<string.h> #include<stdlib.h> #define row 100 #define col 100 static int m[row][col]; char * strrev(char *str) { char *p1, *p2; if (!str || !*str) return str; for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2) { *p1 ^= *p2; *p2 ^= *p1; *p1 ^= *p2; } return str; } int LCS(char *p, char *q, int i, int j) { if (*p == '\0' || *q == '\0') return 0; if (m[i][j] == -1) { if (*p == *q) { m[i][j] = 1 + LCS(p + 1, q + 1, i + 1, j + 1); } else { int a = LCS(p + 1, q, i + 1, j); int b = LCS(p, q + 1, i, j + 1); if (a > b) { m[i][j] = a; } else { m[i][j] = b; } } } return m[i][j]; } void initm() { int i = 0; int j = 0; for (i = 0; i < row; i++) { for (j = 0; j < col; j++) m[i][j] = -1; } } int main() { initm(); char *str_one = "bananas"; char *str_two = (char *) malloc(sizeof(str_one) + 1); strcpy(str_two, str_one); str_two = strrev(str_two); printf("Length of longest common palindrome length is:"); int res = LCS(str_one, str_two, 0, 0); printf("%d \n", res); return 0; }

## Leave a Reply