<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
/**//*
标题:>应试编程实例-[动态规划算法程序设计]
作者:成晓旭
时间:2002年09月15日(18:20:00-21:25:00)
实现“最长公共字符串子序列”问题的动态规划算法实现函数
时间:2002年09月15日(21:31:00-22:00:00)
实现“最长公共字符串子序列”问题的动态规划算法实现函数
*/
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#defineMAXN64//全局最大值常量
//:=========================“最长公共字符串子序列”问题的动态规划法算法=========================
//计算两个字符串序列的最长公共子序列的长度函数
intFirst_Born_SubStr_Len(char*a,char*b,intsubstrlen[][MAXN])
...{
inti,j,m=strlen(a),n=strlen(b);
for(i=0;im;i++)
substrlen[i][0]=0;
for(j=1;jm;j++)
substrlen[0][j]=0;
for(i=1;im;i++)
...{
for(j=1;jn;j++)
if(a[i-1]==b[j-1])
substrlen[i][j]=substrlen[i-1][j-1]+1;
elseif(substrlen[i-1][j]>=substrlen[i][j-1])
substrlen[i][j]=substrlen[i-1][j];
else
substrlen[i][j]=substrlen[i][j-1];
}
return(substrlen[m][n]);
}
//构造最长公共子序列函数
char*Build_First_Born_SubStr(char*a,char*b,charstr[])
...{
intk,i=strlen(a),j=strlen(b),array[MAXN][MAXN];
k=First_Born_SubStr_Len(a,b,array);
str[k]='';
while(k>0)
...{
if(array[i][j]==array[i-1][j])
i--;
elseif(array[i][j]==array[i][j-1])
j--;
else
...{
str[--k]=a[i-1];
i--;
j--;
}
}
return(str);
}
//测试“最长公共字符串子序列”问题的动态规划法函数
voidRun_SubString()
...{
charstr0[MAXN],str1[MAXN],str2[MAXN];
printf("输入第一个字符串(长度",MAXN);
scanf("%s",&str1);
printf("输入第二个字符串(长度",MAXN);
scanf("%s",&str2);
printf("其“最长公共字符串子序列”=%s ",Build_First_Born_SubStr(str1,str2,str0));
}
//:=========================“最长公共字符串子序列”问题的动态规划法算法=========================
intmain(intargc,char*argv[])
...{
//Run_SubString();
Run_Ikebana();
printf(" 应用程序运行结束! ");
return0;
}
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935869
分享到:
相关推荐
“最长公共字符串子序列”问题的动态规划法算法.pdf
字符串子序列
生成一对长随机字母序列,然后确定它们之间的最长公共子串。 在以下示例中,每个原始字符串中都有 10^5 个随机元素。 基地 = 'acgt'; str1 = bases(ceil(rand(1,100000)*4)); str2 =基数(ceil(rand(1,100000)*...
分享一下我写的 “字符串子串替换的函数 int replace_str(const char * src, const char * key_src, const char * key, char ** buf); int replace_count(const char * src, const char * key_src, int * n); int ...
校门外的树、字符串子序列、6种排序算法分析、最长递增子序列,算法分析
关于查找子串的算法。很多数据结构的教科书上都提到或者进行了必要的论述。这里特地摘出来进行详细解释。
该程序用于寻找一串字符串中的子串,并用新的字符串替换,运行环境是C++ builder 6,每行代码都有详细注释
python的快速字符串内核(SSK)实现 字符串内核的实现,如 (又名SSK)中所述。 主要功能是用Cython(具有C类型级别注释的Python)编写的,并且是我所知道的SSK内核的第二快的实现。 我发现最快的SSK实现是Shogun的...
回文最长回文子序列实现了一个程序来查找作为给定输入字符串子序列的最长回文。 例如,给定输入“字符”,程序将返回“carac”。
看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度。显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N)。所以呢,这里...
NULL 博文链接:https://yangkai.iteye.com/blog/585854
用于fortran语言分割字符串和字符串替换的子程序
我自己写的一个运算符重载函数,带有求字符串子串功能
这个 Javascript 库使用最长字符串子序列算法来进行字符串比较。 用 git 克隆: git clone git://github.com/sp4ce/javascript-lcs cd javascript-lcs 代码示例: <!-- Include the library in your ...
C语言处理字符串的分割,处理字符串的拼接已经字符串子串的提取,字符串的匹配查找,链表的使用,插入等操作
主要实现了三种字符串的模式匹配,主要包括字符串子操作的集合,字符串指针回溯,和KMP算法 头文件 #ifndef INDEXHEAD_H_INCLUDED #define INDEXHEAD_H_INCLUDED #include #include #include #define ...
第二个参数to是可选的,它指定了子字符串在原字符串的结束位置(基于0的索引),一般情况下,它应比from大,如果它被省略,那么子字符串将一直到原字符串的结尾处。 如果参数from不小心比参数to大了会怎样?...
基于替换字符串子节的嵌入式所见即所得markdown文档编辑器。 通过基于的可以实现所见即所得。 基本 inline-markdown-editor将包含Markdown的字符串通过双换行符拆分为多个部分,并将每个解析为HTML,然后显示。 ...
PAT tree 在字符串子串匹配 上有这非常优异的表现,这使得它经常成为一种高效的全文检索算法,在自然语言处理领域也有广泛的应用。其算法中最突出的特点就是采用半无限长字串(semi-infinite string 简称 sistring) ...
头歌数据结构数据结构—字符串 第1关子串插入 第2关子串删除 第3关子串定位 第4关子串替换 稳过 早期的计算机主要是用做科学和工程方面的计算。后来随着计算机的发展,非数值型数据的处理工作越来越多,于是有了...