15-2求最大回文的长度

#ifndef PALINDROME_H_
#define PALINDROME_H_
#include<iostream>
#include<string>
int palindrome_longest(char *str,int front,int back); 
#endif 

#include"Palindrome.h"
#define Max(a,b) a>b? a:b 
int palindrome_longest(char *str,int front,int back){
	int pali_count=0; 
	if(front==back)
		return pali_count+1; 
	if(str[front]==str[back]){
		pali_count=palindrome_longest(str,front+1,back-1)+1; 
	}else{
		pali_count=Max(palindrome_longest(str,front+1,back),palindrome_longest(str,front,back-1)); 
	}
	return pali_count; 
}

#include "LongPath.h"
#include "Palindrome.h"
int main(){
	char *str="civic"; 
	char *str0="racecar";
	char *str1="character"; 
	std::cout<<palindrome_longest(str,0,4)<<std::endl; 
	std::cout<<palindrome_longest(str0,0,6)<<std::endl; 
	std::cout<<palindrome_longest(str1,0,8)<<std::endl

在上面的算法中，我们采用了求最长公共子序列一样的算法，也就是《算法导论》第三版 15-4节。

其思想很值得借鉴。对于处理这些“非正规”的子符串问题很有启发性，对于最长公共子序列，并

不是我们以前志熟悉的那种连续性的最长公共子序列，而是求不要求连续性的公共子序列，于是知

我们不能从两个子序列都开始缩进或者退避。

这就是这些问题的特点。

对于这个问题的回文是，我们采用类似的思想，如果相等，那好，他们回文的长度加1，如果不相等，那

只有其中的一端要牺牲一下啦，它要退回一个字符，然后求这两个的最长的那个就行了。

if(str[front]==str[back]){
		pali_count=palindrome_longest(str,front+1,back-1)+1; 
	}else{
		pali_count=Max(palindrome_longest(str,front+1,back),palindrome_longest(str,front,back-1)); 
 }

以上就是核心的代码。永远只牺牲一端。不会同时退避两端。

来自为知笔记(Wiz)