- 浏览: 1404558 次
- 性别:
- 来自: 广州
-
文章分类
最新评论
-
sdgxxtc:
[quo[color=red]te][/color]
C#使用OleDb读取Excel,生成SQL语句 -
zcs302567601:
博主,你好,一直都有个问题没有搞明白,就是 2.x的版本是通过 ...
NGUI所见即所得之UIPanel -
一样的追寻:
感谢楼主!
有向强连通和网络流大讲堂——史无前例求解最大流(最小割)、最小费用最大流 -
cp1993518:
感谢!从你的博客里学到了很多
Unity日志工具——封装,跳转 -
cp1993518:
学习了~,话说现在的版本custom还真的变委托了
NGUI所见即所得之UIGrid & UITable
最长公共子串、最长公共子序列、字符串编辑距离
最长公共子串
问题描述
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。
基本方法
大凡基本方法都是枚举方法,这里其实就枚举所有长度相等的子串进行比较。枚举方法时没有考虑一切实际情况的,这样就有很多“漏洞”,就可以有很多优化的方法。
动态规划
╔
使用dp[i][j]表示 以x[i]和y[j]结尾的最长公共子串的长度,因为要求子串连续,所以对于X[i]与Y[j]来讲,它们要么与之前的公共子串构成新的公共子串;要么就是不构成公共子串。故状态转移方程 X[i] == Y[j],dp[i][j] = dp[i-1][j-1] + 1 X[i] != Y[j],dp[i][j] = 0 对于初始化,i==0或者j==0,如果X[i] == Y[j],dp[i][j] = 1;否则dp[i][j] = 0。这样的处理跟连续子数组最大和有点类似,只是连续子数组子和是当dp[i]<0时执行dp[i]=0。
/* 最长公共子串 DP */ int dp[30][30]; void LCS_dp(char * X, int xlen, char * Y, int ylen) { maxlen = maxindex = 0; for(int i = 0; i < xlen; ++i) { for(int j = 0; j < ylen; ++j) { if(X[i] == Y[j]) { if(i && j) { dp[i][j] = dp[i-1][j-1] + 1; } if(i == 0 || j == 0) { dp[i][j] = 1; } if(dp[i][j] > maxlen) { maxlen = dp[i][j]; maxindex = i + 1 - maxlen; } } } } outputLCS(X); }
后缀数组求解
后缀数组在前面的博文有介绍, 如果将两个字符串连接起来成新字符串,最长公共子串问题就转化为新字符串的最长重复子串的问题(点击前往)了,唯一的区别就是要区别来着同一个字符的最大重复子串。
这里就不在列举了,在处理过程中要对后缀数组进行排序操作,可以考虑重后缀子串的长度的影响——公共子串的长度一定是相等的。
时间复杂度分析
对于基本算法,X的子串(m个)和Y的子串(n个)一一对比,最坏情况下,复杂度为O(m*n*l),空间复杂度为O(1)。
对于动态规划算法,由于自底向上构建最优子问题的解,时间复杂度为O(m*n);空间复杂度为O(m*n),当然这里是可以使用滚动数组来优化空间的,滚动数组在动态规划基础回顾中多次提到。 对于后缀数组方法,连接到一起并初始化后缀数组的时间复杂度为O(m+n),
对后缀数组的字符串排序,由于后缀数组有m+n个后缀子串,子串间比较,故复杂度为O((m+n)*l*lg(m+n)),求得最长子串遍历后缀数组,复杂度为O(m+n),所以总的时间复杂度为O((m+n)*l*lg(m+n)),空间复杂度为O(m+n)。 总的来说使用后缀数组对数据做一些“预处理”,在效率上还是能提升不少的。
╝①
最长公共子序列
问题描述
╔
最长公共子序列就是寻找两个给定序列的子序列,该子序列在两个序列中以相同的顺序出现,但是不必要是连续的。
动态规划求解
使用动态规划求解这个问题,先寻找最优子结构。设X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为两个序列,LCS(X,Y)表示X和Y的一个最长公共子序列,可以看出
- 如果xm=yn,则LCS ( X,Y ) = xm + LCS ( Xm-1,Yn-1 )。
- 如果xm!=yn,则LCS( X,Y )= max{ LCS ( Xm-1, Y ), LCS ( X, Yn-1 ) }
LCS问题也具有重叠子问题性质:为找出X和Y的一个LCS,可能需要找X和Yn-1的一个LCS以及Xm-1和Y的一个LCS。但这两个子问题都包含着找Xm-1和Yn-1的一个LCS,等等。
为了找到最长的LCS,我们定义dp[i][j]记录序列LCS的长度,合法状态的初始值为当序列X的长度为0或Y的长度为0,公共子序列LCS长度为0,即dp[i][j]=0,所以用i和j分别表示序列X的长度和序列Y的长度,状态转移方程为 dp[i][j] = 0 如果i=0或j=0 dp[i][j] = dp[i-1][j-1] + 1 如果X[i-1] = Y[i-1] dp[i][j] = max{ dp[i-1][j], dp[i][j-1] } 如果X[i-1] != Y[i-1] 求出了最长公共子序列的长度后,输出LCS就是输出dp的最优方案了,既可以用一个额外的矩阵存储路径,也可以直接根据状态转移矩阵倒推最优方案。
#include <iostream> using namespace std; /* LCS * 设序列长度都不超过20 */ int dp[21][21]; /* 存储LCS长度, 下标i,j表示序列X,Y长度 */ char X[21]; char Y[21]; int i, j; void main() { cin.getline(X,20); cin.getline(Y,20); int xlen = strlen(X); int ylen = strlen(Y); /* dp[0-xlen][0] & dp[0][0-ylen] 都已初始化0 */ for(i = 1; i <= xlen; ++i) { for(j = 1; j <= ylen; ++j) { if(X[i-1] == Y[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; }else if(dp[i][j-1] > dp[i-1][j]) { dp[i][j] = dp[i][j-1]; }else { dp[i][j] = dp[i-1][j]; } } } printf("len of LCS is: %d\n", dp[xlen][ylen]); /* 输出LCS 本来是逆序打印的,可以写一递归函数完成正序打印 这里采用的方法是将Y作为临时存储LCS的数组,最后输出Y */ i = xlen; j = ylen; int k = dp[i][j]; char lcs[21] = {'\0'}; while(i && j) { if(X[i-1] == Y[j-1] && dp[i][j] == dp[i-1][j-1] + 1) { lcs[--k] = X[i-1]; --i; --j; }else if(X[i-1] != Y[j-1] && dp[i-1][j] > dp[i][j-1]) { --i; }else { --j; } } printf("%s\n",lcs); }
在LCS问题中,如果仅仅要求求出LCS的长度,而不要求输出序列,那么由于每步迭代都只用到了前面的状态,之前的信息便无用了,就可以使用滚动数组了。
#include <iostream> using namespace std; /* 滚动数组 */ int dp[2][21]; /* 存储LCS长度 */ char X[21]; char Y[21]; int i, j, k; void main() { cin.getline(X,20); cin.getline(Y,20); int xlen = strlen(X); int ylen = strlen(Y); for(i = 1; i <= xlen; ++i) { k = i & 1; for(j = 1; j <= ylen; ++j) { if(X[i-1] == Y[j-1]) { dp[k][j] = dp[k^1][j-1] + 1; }else if(dp[k][j-1] > dp[k^1][j]) { dp[k][j] = dp[k][j-1]; }else { dp[k][j] = dp[k^1][j]; } } } printf("len of LCS is: %d\n", dp[k][ylen]); }
╝②
字符串编辑距离
问题描述
╔
字符串编辑距离又叫字符串相似度,编辑距离就是将两个不同的字符串变成相同字符串所需要操作的次数的最小值。而这些操作只有以下三种:
1)修改一个字符
2)增加一个字符
3)删除一个字符
寻找子问题时,我们完全可以像分析最长公共子序列那样分析这个问题,都是“从后向前”看,假设有两个串X=abcdaex,Y=fdfax,它们的最后一个字符是相同的,只要计算X[1,…,6]=abcdae和Y[1,…,4]=fdfa的距离就可以了;但是如果两个串的最后一个字符不相同,那么就可以进行如下的操作来达到目的(xlen和ylen是X串和Y串的长度):
1.一步操作之后,再计算X[1,…,xlen-1]和Y[1,…ylen]的距离。这个操作可以是删除X的最后一个字符,也可以是增加X串的最后一个字符到Y串的最后字符之后
2.一步操作之后,再计算X[1,…,xlen]和Y[1,…ylen-1]的距离。这个操作与情况1类似,反过来而已
3.一步操作之后,再计算X[1,…,xlen-1]和Y[1,…ylen-1]的距离。这个操作可以是修改X串的最后有一个字符为Y串的最后一个字符,后者修改Y的变为X的最后一个字符,使得二者相同。
dp[i][j]中的i和j表示串X和Y的长度,其中,如果某一个串的长度为0,则编辑距离就是另一个串的长度,这很容易理解。状态转移方程为
1.dp[i][j] = 0 如果i=0 & j=0
2.dp[i][j] = xlen | ylen 如果j=0 | i=0
3.dp[i][j] = dp[i-1][j-1] 如果X[i-1] = Y[i-1]
4.dp[i][j] = 1 + min{ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] } 如果X[i-1] != Y[i-1]
下面给出了三种实现方式,第一种是根据分析给出的递归搜索方法;由于具有重叠子问题,所以第二种方法便是使用了备忘录的递归方法(注:分治与动态规划的重要区别就是分治递归不断产生新的子问题,没有重叠子问题;而DP则是在递归不断产生子问题的同时很多子问题是重复计算的,即重叠子问题);第三种便是根据状态转移方程给出了自底向上的实现,这也是最符合DP性质的实现方式。
简单递归搜索
/* 递归搜索 */ int calDistance1(char *ptrX, int xbeg, int xend, char *ptrY, int ybeg, int yend) { if(xbeg > xend) { if(ybeg > yend) return 0; else return yend - ybeg + 1; } if(ybeg > yend) { if(xbeg > xend) return 0; else return xend - xbeg + 1; } if(ptrX[xend] == ptrY[yend]) { return calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1); }else { int t1 = calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend); int t2 = calDistance1(ptrX,xbeg,xend,ptrY,ybeg,yend-1); int t3 = calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1); t1 = t1 < t2 ? t1 : t2; return (t1 < t3 ? t1 : t3) + 1; } }
递归+备忘录
/* 编辑距离 * 设每个字符串长度不超过 30 */ /* 存储子问题的解 i,j表示X,Y长度 * dp[i][j]表示X[0-i)与Y[0-j)的编辑距离 */ int dp[31][31]; /* 自顶向下 & 备忘录 */ int calDistance2(char *ptrX, int xbeg, int xend, char *ptrY, int ybeg, int yend) { if(xend == 0) { if(yend == 0) return 0; else return yend - ybeg + 1; } if(yend == 0) { if(xend == 0) return 0; else return xend - xbeg + 1; } if(ptrX[xend-1] == ptrY[yend-1]) { if(dp[xend-1][yend-1] == 0) { dp[xend-1][yend-1] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1); } return dp[xend-1][yend-1]; }else { int t1, t2, t3; if(dp[xend-1][yend] == 0) { dp[xend-1][yend] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend); } t1 = dp[xend-1][yend]; if(dp[xend][yend-1] == 0) { dp[xend][yend-1] = calDistance2(ptrX,xbeg,xend,ptrY,ybeg,yend-1); } t2 = dp[xend][yend-1]; if(dp[xend-1][yend-1] == 0) { dp[xend-1][yend-1] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1); } t3 = dp[xend-1][yend-1]; t1 = t1 < t2 ? t1 : t2; return (t1 < t3 ? t1 : t3) + 1; } }
自底向上动态规划
/* 编辑距离 * 设每个字符串长度不超过 30 */ /* 存储子问题的解 i,j表示X,Y长度 * dp[i][j]表示X[0-i)与Y[0-j)的编辑距离 */ int dp[31][31]; char X[31]; char Y[31]; /* 自底向上 DP */ int calDistance3(char *ptrX, int xlen, char *ptrY, int ylen) { int i, j; for(i = 1; i <= xlen; ++i) { dp[i][0] = i; } for(j = 1; j <= ylen; ++j) { dp[0][j] = j; } for(i = 1; i <= xlen; ++i) { for(j = 1; j <= ylen; ++j) { if(ptrX[i-1] == ptrY[j-1]) { dp[i][j] = dp[i-1][j-1]; }else { int t1 = dp[i-1][j]; t1 = t1 < dp[i][j-1] ? t1 :dp[i][j-1]; t1 = t1 < dp[i-1][j-1] ? t1 : dp[i-1][j-1]; dp[i][j] = t1 + 1; } } } return dp[xlen][ylen]; }
一并给出测试用例
#include <iostream> using namespace std; void main() { cin.getline(X,30); cin.getline(Y,30); int xlen = strlen(X); int ylen = strlen(Y); printf("%d\n",calDistance1(X,0,xlen-1,Y,0,ylen-1)); //printf("%d\n",calDistance2(X,0,xlen,Y,0,ylen)); printf("%d\n",calDistance3(X,xlen,Y,ylen)); }
╝③
参考:
①勇幸|Thinking: http://www.ahathinking.com/archives/122.html
②勇幸|Thinking: http://www.ahathinking.com/archives/115.html
③勇幸|Thinking: http://www.ahathinking.com/archives/116.html
发表评论
-
C#使用OleDb读取Excel,生成SQL语句
2013-06-27 15:47 10043C#使用OleDb读取Excel,生成SQL语句 ... -
C#读写XML文件工具类——满足一切需求
2013-06-18 07:33 10754C#读写XML文件工具类— ... -
C#解析XML
2013-06-17 19:20 0覆盖 -
C#读取Excel数据动态生成对象并进行序列化
2013-06-16 20:10 7959C#读取Excel数据 ... -
Unity导入unitypackage总是失败问题原因
2013-06-11 22:54 11457最近尝试手游开发,用的Unity引擎,然后开 ... -
C# socket连接服务器发送和接收数据在设置断点单步执行没有问题但是直接运行不能成功
2013-06-04 20:26 5943题目有点长, ... -
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3529在C# 调用Delegate.Create ... -
考题小记(希望能持续增加)
2013-04-03 16:11 0在一块黑板上将123456789重复50次得到450位数12 ... -
数组问题集结号
2012-12-06 22:01 0数组是最简单的数据结构,数组问题作为公司招聘的笔试和面试题目 ... -
算法问题分析笔记
2012-12-05 11:59 01.Crash Balloon Zhejiang Univer ... -
Java基础进阶整理
2012-11-26 09:59 2301Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2613《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
Java文件输出时,文件大小只有24KB
2012-11-14 22:10 1593今天,用Java做点事情,出现了一个很莫名其妙的事情就是文件 ... -
C语言名题精选百则——游戏问题
2012-11-05 23:27 86第8章游戏问题 问题8.1苞数阶魔方阵(MAGIC_O ... -
C语言名题精选百则——序曲
2012-11-04 23:27 2354C语言名题精选百则——序曲 ... -
C语言名题精选百则——数字问题
2012-11-04 23:25 4039C语言名题精选百则——数字问题 尊重他人的劳动, ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法(BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4082尊重他人的劳动,支持原创 本篇博文,D.S.Q ...
相关推荐
这个算法使用动态规划,通过填充一个二维矩阵来计算每对字符的匹配得分,然后找到得分最高的子矩阵,即为最长公共子序列。与fasta算法不同,SW算法不会因为得分低而提前终止,因此它能找出最佳的局部匹配,但计算...
L[i][j] 表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度。 2. 填充数组:从第一行和第一列开始填充,L[0][j] = 0,因为第一个字符串没有字符;同样,L[i][0] = 0,因为第二个字符串没有字符。 ...
// 初始化对角线上的元素,因为字符串与其自身相同时,最长公共子串就是整个字符串 for (int i = 0; i ; i++) { dp[i][i] = 1; maxLength = 1; } // 动态规划过程,遍历所有可能的子串 for (int len = 2; ...
最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要出现在序列比对、文本编辑距离等领域。在两个给定的字符串中,LCS是指不考虑字符顺序的最长子串,它同时存在于这两个字符...
最长公共子序列是指两个或多个序列中,不考虑顺序的最长连续子串,它在各个序列中都存在,但不一定连续。 一、问题定义 给定两个字符串S和T,LCS问题旨在找到这两个字符串的最长子序列,这个子序列不必是连续的,但...
**最长公共子串与最长公共子序列** 1. **最长公共子串**: 是指两个字符串中的最长的相同的子序列,需要连续。例如,字符串"ABABC"和"ABCBDAB"的最长公共子串是"ABC"。 2. **最长公共子序列**: 不要求连续,只...
最长公共子序列(LCS,Longest Common Subsequence)是一个重要的计算机科学概念,特别是在序列比较和算法设计领域。它的定义是指在两个或多个给定序列中,存在一个序列S,它既是这些序列的子序列,并且是所有满足...
5. **动态规划与字符串**:例如Longest Common Subsequence(LCS)最长公共子序列,Longest Palindromic Substring(LPS)最长回文子串,这些问题是动态规划在字符串处理中的经典应用。 6. **字符串排序与压缩**:...
常见的字符串处理包括查找、替换、连接、插入和删除等基本操作,而更深入的算法如最长公共子序列(LCS)和最长公共子串(LIS)则是研究字符串相似性的基础。字符串相似度度量算法如Levenshtein距离提供了一种衡量两个...
LCS 是两个字符串中最长的公共子序列的长度。它不关心字符的相对位置,只关注子序列的长度。LCS 通常用于比较长文本的相似性。 6. **余弦相似度**: 通过计算两个字符串的词袋模型向量之间的夹角余弦值来衡量相似...
5. **最长公共子序列(Longest Common Subsequence, LCS)**:找到两个字符串中的最长子串,它们在各自的字符串中都存在,但不一定连续。LCS的长度可以作为相似度的一个度量。 在Delphi中实现这些算法,你需要理解...
9. **动态规划**:在解决字符串问题时,动态规划常常被用来解决如最长公共子序列、编辑距离等问题。 10. **字符串压缩**:通过对重复字符进行编码,可以实现字符串的压缩,如Run Length Encoding (RLE) 或者霍夫曼...
1. 最长公共子序列:给定两个字符串,找出它们的最长公共子序列。 例如,给定字符串 "ABCBDAB" 和 "BDCABA",它们的最长公共子序列是 "BDABA"。 2. 最长递增子序列:给定一个数组,找出其中的最长递增子序列。 ...
7. **最长公共子序列** 和 **最长公共子串**:找出两个字符串中最长的连续子序列或子串,它们在原始字符串中都存在,这在比较文本或生物序列时非常有用。 8. **Hamming Distance**:如果两个字符串长度相同,...
9. **动态规划和字符串**:在解决一些复杂问题时,如最长公共子序列、编辑距离等,动态规划常与字符串处理结合使用。 通过这个实验,你不仅会掌握数组和字符串的基本操作,还能了解它们在实际问题中的应用。这将为...
常见的编辑距离计算方法有两种:莱文斯坦距离(Levenshtein distance)和最长公共子串长度(Longest common substring length)。莱文斯坦距离允许三种操作:增加、删除和替换字符,而最长公共子串长度仅允许增加和...
常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符...
5. **动态规划**:动态规划方法可以用于解决更复杂的字符串匹配问题,如最长公共子序列(LCS)和编辑距离等。这些问题可以通过构建二维状态转移矩阵来解决。 ### 应用场景 1. **文本编辑器**:在文本编辑器中,...
3. **动态规划**:在处理字符串问题时,动态规划经常被用来解决最长公共子串、最长重复子串、编辑距离等问题。理解状态转移方程和边界条件对于掌握这类问题至关重要。 4. **字符串hash**:通过计算字符串的哈希值,...
通过理解LCS的基本原理,可以进一步扩展到解决其他相关问题,如最长公共子串、编辑距离等。 通过阅读提供的"动态规划实例 最长公共子序列 .docx"文件,你可以深入了解如何在MATLAB中实现这个算法,并通过实例学习...