来源于：http://www.java3z.com/cwbwebhome/article/article18/report92.html?id=4867
回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。现在的任务是，求出将给定字符串变成回文词所需要插入的最少字符数
。比如:“Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。
[输入]:
第一行:字符串的长度N(3 <= N <= 5000)
第二行:需变成回文词的字符串
[输出]：
将给定字符串变成回文词所需要插入的最少字符数
[样例]:
Sample Input
5
Ab3bd
Sample Output
2
分析：
S和S' (注:S'是S的反串)的最长公共子串其实一定是回文的。这样我们就可以借助lcs来解决该题，即用s的长度减去lcs的值即可。
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader (System.in));
int total = Integer.parseInt(in.readLine());
String string = in.readLine();
System.out.println(total-LCS(string,new StringBuffer(string).reverse().toString()));
}
//返回两个string的lcs的长度
public static int LCS(String str1,String str2){
short length1 = (short)str1.length();
short length2 = (short)str2.length();
short[][]result = new short [2][length2+1]; //滚动数组,节省空间
for(int i=1;i<=length1;i++){
for(int j=1;j<=length2;j++){
if(str1.charAt(i-1)==str2.charAt(j-1))
result[i%2][j] = (short)(result[(i-1)%2][j-1]+1);
else
result[i%2][j] = result[(i-1)%2][j]>result[i%2][j-1]?result[(i-1)%2][j]:result[i%2][j-1];
}
}
return result[length1%2][length2];
}
}
由求lcs算法设计到具体实现源码：
来源于：http://blog.csdn.net/fightforyourdream/article/details/20015641 讲解的非常详细
LCS：又称 最长公共子序列。 其中子序列(subsequence)的概念不同于串的子串。它是一个不一定连续但按顺序取自字符串X中的字符序列。 例如：串"AAAG"就是串“CGATAATTGAGA”的一个子序列。
字符串的相似性问题可以通过求解两个串间的最长公共子序列(LCS)来得到。 当然如果使用穷举算法列出串的所有子序列，一共有2^n种，而每个子序列是否是另外一个串的子序列又需要O(m)的时间复杂度，因此这个穷举的方法时间复杂度是O(m*(2^n))指数级别，效率相当的可怕。我们采用动态规划算法来解决这个问题。
假如我们有两个字符串：X=[0,1,2....n] Y=[0,1,2...m]。我们定义L(i, j)为X[0...i]与Y[0...j]之间的最长公共子序列的长度。通过动态规划思想(复杂问题的最优解是子问题的最优解和子问题的重叠性质决定的)。我们考虑这样两种情况：
(1) 当X[i]=Y[j]时， L(i, j)=L(i-1, j-1)+1 。证明很简单。
(2) 当X[i]!=Y[j]时， 说明此事X[0...i]和Y[0...j]的最长公共子序列中绝对不可能同时含有X[i]和Y[j]。那么公共子序列可能以X[i]结尾，可能以Y[j]结尾，可以末尾都不含有X[i]或Y[j]。因此
L(i, j)= MAX{L(i-1 , j), L(i, j-1)}
package DP;
public class LCS2 {
/** 字符串X的字符数组 */
private char[] charArrayX = null;
/** 字符串Y的字符数组 */
private char[] charArrayY = null;
public LCS2(String sa, String sb) {
charArrayX = new char[sa.length() + 1];
System.arraycopy(sa.toCharArray(), 0, charArrayX, 1, sa.length());
charArrayY = new char[sb.length() + 1];
System.arraycopy(sb.toCharArray(), 0, charArrayY, 1, sb.length());
}
/**
* 得到最长公共子序列的长度
*/
public void getLCS() {
int[][] length = new int[charArrayX.length + 1][charArrayY.length + 1];
for (int m = 1; m < charArrayX.length; m++) {
for (int n = 1; n < charArrayY.length; n++) {
if (charArrayX[m] == charArrayY[n]) {
length[m][n] = length[m - 1][n - 1] + 1;
} else
length[m][n] = max(length[m - 1][n], length[m][n - 1]);
// length[m][n] = max(length[m][n], length[m-1][n-1]);
}
}
for (int m = 0; m < charArrayX.length; m++) {
for (int n = 0; n < charArrayY.length; n++) {
System.out.print(length[m][n] + " ");
}
System.out.println();
}
// 打印最长公共子序列
String lcstr = "";
int x = charArrayX.length - 1;
int y = charArrayY.length - 1;
while (x >= 1 && y >= 1) {
if (charArrayX[x] == charArrayY[y]) {
lcstr = charArrayX[x] + lcstr;
x--;
y--;
} else {
if (length[x - 1][y] <= length[x][y - 1]) // 往值较大的路径走
y--;
else
x--;
}
}
System.out.println("最长公共子序列为：" + lcstr + " [length=" + lcstr.length()
+ "]");
}
/**
* 取最大值
*/
private int max(int m, int n) {
return m > n ? m : n;
}
/**
* 测试
*/
public static void main(String[] args) {
LCS2 lcs = new LCS2("GTTCCTAATA", "CGATAATTGAGA");
lcs.getLCS();
}
}
问题拓展：设A,B,C是三个长为n的字符串，它们取自同一常数大小的字母表。设计一个找出三个串的最长公共子串的O(n^3)的时间算法。 (来自《Algorithm Design》(中文版：算法分析与设计) - Chapter9 - 文本处理 - 创新题C-9.18）
public class TriLCS{
char[] charA=null;
char[] charB=null;
char[] charC=null;
public TriLCS(String sa,String sb,String sc){
charA=new char[sa.length()+1];
System.arraycopy(sa.toCharArray(),0,charA,1,sa.length());
charB=new char[sb.length()+1];
System.arraycopy(sb.toCharArray(),0,charB,1,sb.length());
charC=new char[sc.length()+1];
System.arraycopy(sc.toCharArray(),0,charC,1,sc.length());
}
public void getTriLCS(){
int[][][] length=new int[charA.length][charB.length][charC.length];
for(int a=1;a<charA.length;a++)
for(int b=1;b<charB.length;b++)
for(int c=1;c<charC.length;c++){
if(charA[a]==charB[b]&&charA[a]==charC[c]){
length[a][b][c]=length[a-1][b-1][c-1]+1;
}
else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
length[a][b][c]=max(length[a-1][b-1][c],length[a][b][c-1]);
}
else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
length[a][b][c]=max(length[a-1][b][c-1],length[a][b-1][c]);
}
else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
length[a][b][c]=max(length[a][b-1][c-1],length[a-1][b][c]);
}
else{
length[a][b][c]=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
}
}
//打印最长公共子序列
String lcstr="";
int a=charA.length-1;
int b=charB.length-1;
int c=charC.length-1;
while(a>=1&&b>=1&&c>=1){
if(charA[a]==charB[b]&&charA[a]==charC[c]){
lcstr=charA[a]+lcstr;
a--;
b--;
c--;
}
else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
if(length[a-1][b-1][c]<=length[a][b][c-1])
c--;
else{
a--;
b--;
}
}
else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
if(length[a-1][b][c-1]<=length[a][b-1][c])
b--;
else{
a--;
c--;
}
}
else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
if(length[a][b-1][c-1]<=length[a-1][b][c])
a--;
else{
b--;
c--;
}
}
else{
int maxize=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
if(maxize==length[a-1][b][c])
a--;
if(maxize==length[a][b-1][c])
b--;
if(maxize==length[a][b][c-1])
c--;
if(maxize==length[a-1][b-1][c]){
a--;
b--;
}
if(maxize==length[a-1][b][c-1]){
a--;
c--;
}
if(maxize==length[a][b-1][c-1]){
b--;
c--;
}
}
}
System.out.println("最长子串为："+lcstr+"(length="+length[charA.length-1][charB.length-1][charC.length-1]+")");
}
/**
* 取最大值
*/
private int max(int m,int n){
return m>n?m:n;
}
/**
* 取最大值
*/
private int max(int x,int y,int z,int k,int m,int n){
int maxizen=0;
if(maxizen<x) maxizen=x;
if(maxizen<y) maxizen=y;
if(maxizen<z) maxizen=z;
if(maxizen<k) maxizen=k;
if(maxizen<m) maxizen=m;
if(maxizen<n) maxizen=n;
return maxizen;
}
public static void main(String[] args){
TriLCS tri=new TriLCS("aadsbbbcs","adsabcs","adbsbsdcs");
tri.getTriLCS();
}
}
相关推荐
- 应用领域：LCS算法不仅可以用于文本分析中的相似度比较，还可以应用于生物信息学，如基因序列的对比分析。 - **马纳克算法** - 算法介绍：马纳克算法是一种高效的线性时间算法，专门用于查找序列中的最长回文...
java笔试题回文子串LPS-LCS-算法-分析 最长公共子串（LCS）问题是一直使用的经典计算问题。 该项目探索 LCS，它的一个特例，最长回文子串 (LPS) 问题，以及它的概括以及不同的问题域如何影响算法性能。 我对这些问题...
《算法导论》是计算机科学领域的一本经典著作，它深入浅出地介绍了各种重要的算法，并提供了详尽的分析和实现。在这个名为“cpp-算法导论第三版中算法的C实现”的压缩包中，我们可以期待找到《算法导论》第三版中所...
"cpp-C常用算法实现集锦"是一个非常实用的资源，它包含了多种常见算法的C++实现，这对于学习和参考具有很高的价值。 1. **排序算法**： - **冒泡排序**：基础的排序算法，通过不断交换相邻元素实现排序。 - **...
使用动态规划的两种方式实现的LCS（最大公共串）（下面的算法都会使用动态规划的两种方式来实现） 加权有向无环图中最短路径和最长路径 背包问题 最长回文子串(lps) ###幂乘：算法复杂度是O(lgn) ##贪心算法 活动...
基于Python实现的数据结构与算法完整源代码+超详细注释(包含46个作业项目) 项目包含： 01_变位词问题 02_python数据类型的性能 03_python实现ADT Stack 04_栈的应用1括号匹配 05_栈的应用2十进制转二进制 06_栈的...
以上知识点涉及算法和数据结构的核心概念、经典算法问题的解题策略、以及实际应用中的问题解决方案。适合对算法感兴趣，并希望在面试中大显身手的程序员。此外，也包含了学习资源和平台的推荐，有助于读者更系统和...
在编程领域，C语言因其高效、灵活和接近底层的特性，常常被用来实现各种算法。"C常用算法程序集"是一份宝贵的资源，它包含了多种常见的算法实现，可以帮助程序员加深对算法的理解，提升编程能力。下面，我们将深入...
在这个压缩包中包含的四个C程序分别涉及到了马鞍点、最长回文子串、最长公共子序列以及最大子集问题，这些都是计算机科学中经典且重要的算法问题。下面我们将逐一探讨这些知识点。 首先，"马鞍点"是指在矩阵中的一...
2. 插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。 3. 选择排序：每次从未排序的元素中找到最小（或最大）的一个元素，存放到排序序列的起始位置。 4. 快速排序：利用分治法...
Java算法大全是一个全面涵盖近100种算法的资源包，专为Java程序员设计，旨在提升他们的算法理解和实现能力。这个压缩包包含了丰富的算法实例、解释和代码，可以帮助开发者深入理解算法背后的逻辑，并能有效地应用到...
Java作为一种广泛使用的编程语言，拥有丰富的库支持和强大的性能，使得它成为实现算法的理想平台。 1. **排序算法**： - 冒泡排序：通过不断交换相邻的逆序元素来排序数组。 - 插入排序：将未排序的元素逐个插入...
3. Manacher's Algorithm：针对回文串查找的优化算法，能在线性时间内找到字符串中最长的回文子串。 七、计算几何 1. 平面直角坐标系内的点、线段、多边形的判断和操作，如点在线上、线段相交、凸包问题等。 2. 圆...
本资源"java常见算法汇总"旨在提供一系列Java实现的经典算法，帮助开发者巩固基础，提升编程能力。 1. **排序算法**： - 冒泡排序：简单的交换排序，时间复杂度为O(n^2)。 - 选择排序：每次选择最小元素并放到...
**NOIP基本算法必背** 全国青少年信息学奥林匹克联赛（NOIP）是一项旨在培养青少年计算机编程能力的竞赛，其中算法是考察的重点。本资源“noip基本算法必背”为参赛者提供了NOIP中常见的算法知识，对于提高解题能力...
- 欧拉素数筛选、合数分解为素数、费马小定理（乘法逆元）、日期差计算、基姆拉尔森公式（求星期几）、组合大小计算（求C(n,m)）、GCD（辗转相除法）、快速幂、矩阵乘法、大数运算、回文数、三类博弈论和母函数等。...
这些竞赛通常涉及到一系列算法问题，要求参赛者快速、准确地编写代码来解决问题。入门级算法模板是帮助新手熟悉常见算法和编程技巧的宝贵资源。以下是一些基本的算法知识和模板，适用于ACMer初学者： 1. **排序算法...
在编程领域，C语言因其高效、灵活和接近底层的特点，被广泛用于开发系统软件和算法实现。"C 常用算法程序集"这个资源显然集合了多种常见算法的C语言实现，对于学习和理解算法有着重要的价值。下面将详细讨论这些算法...
在本资源中，我们主要关注的是一个以Java编程语言实现的算法集合，涵盖了近百种不同的算法。这个压缩包提供了一套完整的源代码实例，对于学习和理解计算机科学中的各种算法有着极大的帮助。以下是对其中可能包含的...