首先理解题意，回文串的特点：倒序后跟原串相同。故而可以将原串看成向一个回文串在任意位置添加任意字符后形成的字符串，也就是说原串中存在一段未必连续的回文序列。

通过分析可以知道AC本题的核心思路：求出回文序列的长度，用原串的长度减去其长度即可。

要求出回文序列的长度，肯定要利用回文串的特点，故而想到求原串和其反串的最长公共子序列（不一定连续）。

所以可以采用文本比较算法中的Needleman/Wunsch算法（动态规划思想）：

定义：

　　LCS(A,B)表示字符串A和字符串B的最长公共子串的长度。很显然，LSC(A,B)=0表示两个字符串没有公共部分。

　　Rev(A)表示反转字符串A

　　Len(A)表示字符串A的长度

　　A+B表示连接字符串A和字符串B

　　性质：

　　LCS(A,A)=Len(A)

　　LCS(A,"")=0

　　LCS(A,B)=LCS(B,A)

　　0≤LCS(A,B)≤Min(Len(A),Len(B))

　　LCS(A,B)=LCS(Rev(A),Rev(B))

　　LCS(A+C,B+C)=LCS(A,B)+Len(C)

　　LCS(A+B,A+C)=Len(A)+LCS(B,C)

　　LCS(A,B)≥LCS(A,C)+LCS(B,C)

　　LCS(A+C,B)≥LCS(A,B)+LCS(B,C)

　　为了讲解计算LCS(A,B)，特给予以下几个定义

　　A=a₁a₂……a_N，表示A是由a₁a₂……a_N这N个字符组成，Len(A)=N

　　B=b₁b₂……b_M，表示B是由b₁b₂……b_M这M个字符组成，Len(B)=M

　　定义LCS(i,j)=LCS(a₁a₂……a_i,b₁b₂……b_j)，其中0≤i≤N，0≤j≤M

　　故：　　LCS(N,M)=LCS(A,B)

　　　　　　LCS(0,0)=0

　　　　　　LCS(0,j)=0

　　　　　　LCS(i,0)=0

　　对于1≤i≤N，1≤j≤M，有公式一

　　若a_i=b_j，则LCS(i,j)=LCS(i-1,j-1)+1

　　若a_i≠b_j，则LCS(i,j)=Max(LCS(i-1,j-1),LCS(i-1,j),LCS(i,j-1))=Max（LCS(i-1,j),LCS(i,j-1))

　　计算LCS(A,B)的算法有很多，下面介绍的Needleman/Wunsch算法是其中的一种。和LD算法类似，Needleman/Wunsch算法用的都是动态规划的思想。在Needleman/Wunsch算法中还设定了一个权值，用以区分三种操作（插入、删除、更改）的优先级。在下面的算法中，认为三种操作的优先级都一样。故权值默认为1。

　　举例说明：A=GGATCGA，B=GAATTCAGTTA，计算LCS(A,B)

　　第一步：初始化LCS矩阵

　　第二步：利用公式一，计算矩阵的第一行

　　第三步：利用公式一，计算矩阵的其余各行

　　则，LCS(A,B)=LCS(7,11)=6

--------------------------------------------------我是分割线---------------------------------------------------------------

AC代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 #define MAX 1100

 int LCS[MAX][MAX];

 string s1, s2;

 int i, j;

 int maxOfAll(int a, int b, int c)

 {

     return max(max(a, b), c);

 }

 int main()

 {

     while(cin >> s2)

     {

         s1 = s2;

         size_t len = s1.length();

         for(int ix = ; ix <= len; ++ix)

             LCS[ix][] = LCS[][ix] = ;

         reverse(s2.begin(), s2.end());

         for(i = ; i <= len; ++i)

         {

             for(j = ; j <= len; ++j)

             {

                 if(s1[i-] == s2[j-])

                     LCS[i][j] = LCS[i-][j-] + ;

                 else

                     LCS[i][j] = maxOfAll(LCS[i-][j], LCS[i-][j-], LCS[i][j-]);

             }

         }

         cout << len-LCS[len][len] << endl;

     }

 }

 import java.util.*;

 public class Main {

     public static void main(String[] args) {

         Scanner sc = new Scanner(System.in);

         while(sc.hasNext()) {

             String s1 = sc.next();

             String s2 = new StringBuffer(s1).reverse().toString();

             int [][] dp = new int[s1.length()+1][s2.length()+1];

             for (int i = 1; i < dp.length; ++i) {

                 for (int j = 1; j < dp[0].length; ++j) {

                     dp[i][j] = s1.charAt(i-1) == s2.charAt(j-1) ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);

                 }

             }

             System.out.println(s1.length() - dp[s1.length()][s2.length()]);

         }

         sc.close();

     }

 }

最新文章

1. Perplexity Vs Cross-entropy
2. R语言：用简单的文本处理方法优化我们的读书体验
3. 使用spring连接及操作mongodb3.0
4. 2016年11月17日--SQL主、外键，子查询
5. Week1 学长的经验教训
6. JavaBean基础转载
7. 一步一步理解GB、GBDT、xgboost
8. 从今天开始每天刷一题，并写在这里 分类： ACM 2015-06-16 23:52 14人阅读 评论(0) 收藏
9. 查找数N二进制中1的个数（JS版 和 Java版）
10. 去掉url后面的#
11. 使用SQL SERVER 来自动发送邮件
12. jar包内的文件导出的注意点
13. 数据处理 array json 格式 转换成 数组形式
14. Mybatis复杂嵌套关联一例
15. Java基础十--接口
16. [UE4]acotor放置4*4列表
17. 4. Median of Two Sorted Arrays(2个有序数组的中位数)
18. 非在线PDF转图片！！！
19. .NET FrameWork 中的 CTS
20. WPF TabItem.Collapse 的问题

热门文章

1. 简单cookie入侵
2. CEILING保留n位小数向上取整
3. [JZOJ4737] 【NOIP2016提高A组模拟8.25】金色丝线将瞬间一分为二
4. gedit 外部工具——快捷运行
5. 13.多级代理下Nginx透传真实IP
6. redis之Scan
7. Canonical 开源 MicroK8 | 云原生生态周报 Vol. 25
8. epoll(2) 源码分析
9. Linux下终端字体颜色设置方法
10. numpy+pandas+ matplotlib模块(day18)