#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)
转载于:https://www.cnblogs.com/yml435/p/4655525.html
