- 浏览: 1397360 次
- 性别:
- 来自: 广州
文章分类
最新评论
-
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 9959C#使用OleDb读取Excel,生成SQL语句 ... -
C#读写XML文件工具类——满足一切需求
2013-06-18 07:33 10705C#读写XML文件工具类— ... -
C#解析XML
2013-06-17 19:20 0覆盖 -
C#读取Excel数据动态生成对象并进行序列化
2013-06-16 20:10 7877C#读取Excel数据 ... -
Unity导入unitypackage总是失败问题原因
2013-06-11 22:54 11416最近尝试手游开发,用的Unity引擎,然后开 ... -
C# socket连接服务器发送和接收数据在设置断点单步执行没有问题但是直接运行不能成功
2013-06-04 20:26 5878题目有点长, ... -
C# 调用Delegate.CreateDelegate方法出现“未处理ArgumentException”错误解决
2013-05-31 12:24 3477在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 2259Java学习笔记整理 ... -
Java学习笔记整理
2012-11-24 23:43 211Java学习笔记整理 本文档是我个人 ... -
《C++必知必会》学习笔记
2012-11-24 23:40 2572《C++必知必会》学 ... -
《C++必知必会》学习笔记
2012-11-24 23:34 1《C++必知必会》学习笔 ... -
Java文件输出时,文件大小只有24KB
2012-11-14 22:10 1544今天,用Java做点事情,出现了一个很莫名其妙的事情就是文件 ... -
C语言名题精选百则——游戏问题
2012-11-05 23:27 86第8章游戏问题 问题8.1苞数阶魔方阵(MAGIC_O ... -
C语言名题精选百则——序曲
2012-11-04 23:27 2317C语言名题精选百则——序曲 ... -
C语言名题精选百则——数字问题
2012-11-04 23:25 3976C语言名题精选百则——数字问题 尊重他人的劳动, ... -
C语言名题精选百则——排序
2012-11-04 23:29 128第5章排 序 问题5.1 二分插入法(BIN ... -
C语言名题精选百则——查找
2012-11-04 23:29 4033尊重他人的劳动,支持原创 本篇博文,D.S.Q ...
相关推荐
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
用本程序可得到字符串的相似度和字符串的公共子串以及编辑距离。
在随意给出的2个字符串中,找出它们共同的最长的子串。 【输入】 输入文件的第一行为一个整数2,接下来有2行,每行为一个字符串,每个字符串的长度均小于255。 【输出】 输出只有一行,即:共同的最长子串,若有多个...
本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法。分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= ,L1=s1.length,L2=s2....
求N个字符串的最长公共子串,N,字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长公共子串为“local...
主要介绍了java实现求两个字符串最长公共子串的方法,是一道华为OJ上的一道题目,涉及Java针对字符串的遍历、转换及流程控制等技巧,需要的朋友可以参考下
查找两个字符串a,b中的最长的公共子串,并将结果输出
主要介绍了PHP实现求两个字符串最长公共子串的方法,涉及php字符串与数组的遍历、运算、判断等相关操作技巧,需要的朋友可以参考下
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串。 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题...
最长公共子序列的算法实现,采用递归方法。
输入一个字符串,将输出该字符串最长对称子串及其长度,很精巧的算法
LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置...
今天小编就为大家分享一篇python实现求两个字符串的最长公共子串方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
两个字符串里求最长的公共子串
MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的非空字符串。 输出格式: 在...
输入两个字符串, 求它们最长公共字串的长度
请编写一个函数,输入两个字符串,求它们的最长公共子序列,并打印出最长公共子序列。 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子序列,则输出它们的长度4,并打印任意一个子...