1.回文串的实现要求
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。 如何删除才能使得回文串最长呢？ 输出需要删除的字符个数。
5.实现分析
比较简单的想法就是求原字符串和其反串的最大公共子串的长度，然后用原字符串的长度减去这个最大公共子串的长度就得到了最小编辑长度。 （注：最大公共子串并不一定要连续的，只要保证出现次序一致即可看作公共子串） 可以使用 Needleman/Wunsch算法 ,牺牲内存换取简单的代码和CPU时间。
6.实现代码
#include<iostream> #include<string> #include<algorithm> using namespace std; const int MAX = 1001; int MaxLen[MAX][MAX]; //最长公共子序列，动态规划求法 int maxLen(string s1, string s2){ int length1 = s1.size(); int length2 = s2.size(); for (int i = 0; i <= length1; ++i) MaxLen[i][0] = 0; 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230243.html原文链接：https://javaforall.net
