最大公共子串.doc

《最大公共子串.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、依据上面的分析，那么我们主要就是要找到两字符串的公共字符串的大小，然后用两字符串的长度的少大值减去它就可以了。也就是：编辑距离=max(字符串1的长度,字符串2的长度)-两字符串的最长公共长度。好的，现在重点就是要计算两字符串的最长公共长度。我是这样考虑的，如果要计算str1与str2的最长公共长度。我首先从str1的字符从左到右一个个来，假设str1前m个字符与str2前n个字符的最长公共长度为dist[m][n]，那么假设str1前m+1个字符与str2前n+1个字符的最长公共长度就为以下两种情况了:（1）str1[m+1]==str2[n+1]，这个时候的dis

2、t[m+1][n+1]就应该是dist[m][n]+1了；(2)str1[m+1]!=str2[n+1]，这个时候的dist[m+1][n+1]就应该是dist[m][n+1]和dist[m+1][n]中较大点的那个了。好了，就是这样思想，这是一种动态规划的想法，下面给出动态规划状态转移方程：dist[m][n]=(1):dist[m-1][n-1],str1[m]==str2[n];(2):max(dist[m-1][n],dist[m][n-1]),else代码1：//求解两字符串的编辑距离publicstaticintEditDistance(Stringstr

3、1,Stringstr2){char[]strs1=str1.toCharArray();//转换为字符数组char[]strs2=str2.toCharArray();//转换为字符数组int[][]dist=newint[strs1.length+1][strs2.length+1];//定义距离二维数组,多定义一维是为了避免边界检测inti,j,temp;for(i=0;i<=strs1.length;i++)dist[i][0]=0;//初始化边界值for(i=0;i<=strs2.length;i++)dist[0][i]=0;//初始化边界值for(i=1

4、;i<=strs1.length;i++){for(j=1;j<=strs2.length;j++){if(strs1[i-1]==strs2[j-1])//如果两字符相等，则取dist[i-1][j-1]+1{temp=dist[i-1][j-1]+1;}else//不等，则取dist[i-1][j]与dist[i][j-1]的最大值{temp=dist[i][j-1];if(dist[i-1][j]>temp)temp=dist[i-1][j];}dist[i][j]=temp;}}temp=dist[strs1.length][strs2.length];if(

5、strs1.length>strs2.length)returnstrs1.length-temp;elsereturnstrs2.length-temp;}对这个程序作出时空分析的时候发现，时间复杂度为O(mn)，空间复杂度也为O(mn)，有没有改进的余地呢？其实还是有的。注意到，每次状态转移的时候，我们只需考虑dist[i-1][*]这一维数组和dist[i][*]这一维，所以我们时候只用两个一维数组就可以了呢，然后使用两个数组一次轮倒(轮倒是我创造的词，意思就是轮流的倒来倒去)，其实都不用轮倒，只要每次把[i][*]的结果用[i-1][*]保存就好了！