Here is my simple recursive implementation for this issue.
Without full test.
If any bug, please let me know. thank you so much.
Anybody could show me a non-recursive right implementation for this question?
On internet, many implementation can not pass my simple test.
And I spent much time on this issue and no good resolution gained even now.
So, I hope you can write a nice non-recursive one and post on this page. thank you again.
the best from Jonsen.
#include <stdio.h>
#include <string.h>
static int len = 0;
static char* str = NULL;
/**
* find all possible palindromes starting with str[m]
*/
int scan(int m, int n){
if(m > n) return 0;
int i = m, j = n;
while(i < j){
if(str[i] == str[j]) { i++; j--; }
else break;
}
if(i >= j) return n-m+1;
else return scan(m, n-1);
}
/**
* process str starting with m and ending with n.
* then, process str starting with m+1, and ending with n.
* if length of string is smaller than len gained, there is
* no need to process the str anymore and avoiding useless
* processing.
*/
void process(int m, int n){
printf("process(%d, %d)\n", m, n);
if(m > n) return;
int tmp = scan(m, n);
printf("scan(%d, %d) and rtv = %d\n", m, n, tmp);
len = tmp > len ? tmp : len;
if(n-m > len) process(m+1, n);
}
int main(int argc, char* argv[]){
str = argv[1];
process(0, strlen(str) - 1);
printf("len = %d\n", len);
return 0;
}
Running log:
[root@localhost tmp]# gcc longest_palindrome_substring.c && time a.out abcabcddcbbcddcba
process(0, 16)
scan(0, 16) and rtv = 1
process(1, 16)
scan(1, 16) and rtv = 1
process(2, 16)
scan(2, 16) and rtv = 1
process(3, 16)
scan(3, 16) and rtv = 14
len = 14
real 0m0.001s
user 0m0.000s
sys 0m0.001s
[root@localhost tmp]#