位置:首页 » 技术 » 求两个字符串的最大公共字串

求两个字符串的最大公共字串

日期:2013-07-02 阅读:0num
Advertisement
//今天面试遇到一个有趣的题目 取两个字符串的最大公共字符串
//解决方案如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//先造一个常用函数
char* strsub( char const* pStrSrc, int iStart, int iLen )
{
    if( !pStrSrc || iStart <  0 )
        return NULL;

    int iStrLen = strlen( pStrSrc );

    char* pStrRes = NULL;
    if( iLen >= iStrLen - iStart )
    {
        pStrRes = (char*)malloc( iStrLen - iStart + 1 );

        if( !pStrRes )
            return NULL;

        memset( pStrRes, 0,  iStrLen - iStart + 1 );

        strncpy( pStrRes, pStrSrc + iStart, iStrLen  - iStart );

        return pStrRes;
    }
    else
    {
        pStrRes = (char*)malloc( iLen + 1 );

        if( !pStrRes )
            return NULL;

        memset( pStrRes, 0, iLen + 1 );

        strncpy( pStrRes, pStrSrc + iStart, iLen );

        return pStrRes;

    }

}

char* maxComm( char* pStrLeft, char* pStrRight )
{
    if( !pStrLeft || !pStrRight )
    {
        return NULL;
    }

    char* pStrLess = NULL;
    char* pStrMore = NULL;
    char* pStrRes= NULL;

    int iLeft = strlen( pStrLeft );
    int iRight = strlen( pStrRight );

    int iLess = ( iLeft <= iRight ) ? iLeft : iRight;

    int i,j;

    if( iLeft <= iRight )
    {
        pStrLess = pStrLeft;
        pStrMore = pStrRight;
    }
    else
    {
        pStrLess = pStrRight;
        pStrMore = pStrLeft;
    }
    char* pSt = NULL;

    for( i = iLess; i > 0; i-- )
    {
        for( j = 0; j <= iLess - i; j++ )
        {
            pStrRes = strsub( pStrLess, j, i );

            if( strstr( pStrMore, pStrRes ) )
                return pStrRes;

            free( pStrRes );
            pStrRes = NULL;
        }
    }

    return NULL;
}

int main( int argc, char** argv )
{
    char* pStrLeft = "adasdfabc";
    char* pStrRight = "asdabcasdf";

    puts( "max comm string between two strings" );
    char* strMaxComm = maxComm( pStrLeft, pStrRight );
    printf( strMaxComm );
    puts( "" );

    free( strMaxComm );
    strMaxComm = NULL;

    return 0;
}
相关文章
  • 求两个字符串的最大公共字串

    //今天面试遇到一个有趣的题目 取两个字符串的最大公共字符串 //解决方案如下: #include <stdio.h> #include <stdlib.h> #include <string.h> //先造一个常用函数 char* strsub( char const* pStrSrc, int iStart, int iLen ) { if( !pStrSrc || iStart < 0 ) return NULL; int iStrLen = strlen(

  • 求两个字符串差异程度的算法解决方案

    求两个字符串差异程度的算法 不是LCS,不是求最长公共字串.要求两字符串有差异的字符个数.例如: aaaaabaaaaa aaaaacaabaa 这两个字符串,最大公共字串长度是5,但它们只有两个字符不同,函数输出值应为2. 如果是: aaabbbcccddd aaaeeeddd 函数的输出值应该是6. 比较形象地形容一下,把两个字符串排成上下两行,每个字符串都可以在任何位置插入空格以便上下对齐,每个列上至少有一个字符来自这两个字符串.当对齐程度最高的时候,没有对上的列的数即为函数输出值. aa

  • 华为OJ——公共字串计算

    题目描述 题目标题: 计算两个字符串的最大公共字串的长度,字符不区分大小写 详细描述: 接口说明 原型: intgetCommonStrLength(char*pFirstStr,char*pSecondStr); 输入参数: char*pFirstStr//第一个字符串 char*pSecondStr//第二个字符串 输入描述: 输入两个字符串 输出描述: 输出一个整数 输入例子: asdfas werasdfaswer 输出例子: 6 import java.util.*; public c

  • 求两个字符串的最长公共子串(LCS)

    最长公共子串(LCS),有三种情况:1.公共子串的元素必须相邻. 2.公共子串的元素可以不相邻联单3. 求多个字符串而不是两个字符串的最长公共子串 1.公共子串的元素必须相邻: LCS问题就是求两个字符串最长公共子串的问题.解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0.然后求出对角线最长的1序列,其对应的位置就是最长匹配子串的位置. 下面是字符串21232523311324和字符串312123223445的匹配矩阵,前者为X方向的,后者为Y方向的

  • C++入门程序:求两个字符串的最长公共字串。c++新手求解。解决思路

    C++入门程序:求两个字符串的最长公共字串.c++新手求解. 题目: 类和对象的编程 求两个字符串的最长公共子串. 要求:输入两个字符串,输出它们的最长公共子串,包括长度. 设计一个类String,包括一个len(字符串长度)和字符串指针s.另有如下成员函数 void getstring ( ) 从用户获取一个字符串 void display ( ) 输出字符串. 举例: 输入字符串s1:this is a string 输入字符串s2:my string is abc s1 和s2最长公共子字

  • 求两个字符串的最长公共子串 (字母务须相邻)

    求两个字符串的最长公共子串 (字母必须相邻) 上一篇<求最长公共子串(可以不相邻)>的另一种变换题目,这个相对于上一篇,稍稍简单,不过这个算法的时间复杂度不太好,更简单的算法,有时间我再整理下. 问题:求最长公共子串,字符必须相邻. 代码: public class common { public static void findCommon(String s1, String s2) { int i;//第一个游标从0 ~ length-1游走 int j;//第二个游标从i+1 ~ len

  • 求两个字符串的最长公共子串(字母可以不紧邻,但是顺序不变)

    求两个字符串的最长公共子串(字母可以不相邻,但是顺序不变) 不知道为什么笔试总是遇到这些题目,看来经典算法,大家都喜欢啊,这个是LCS问题,动态规划. 问题:求两个字符串的最长公共子串,字母可以不相邻,但是顺序不变 代码: public class lcs { public static void LCS_Print(String str1, String str2) { int length1 = str1.length(); int length2 = str2.length(); int

  • 算法导论中怎么求两个字符串的最长公共子序列

    算法导论中如何求两个字符串的最长公共子序列 #include<iostream> #include<string> using namespace std; const int max_length=10; void print(int b[max_length][max_length],string X,int i,int j); void LCS(string X,string Y,int b[max_length][max_length],int m,int n ) { in

  • 求两个字符串的最长公共接续子序列(SAM实现)

    求两个字符串的最长公共连续子序列(SAM实现) //时间复杂度O(N) #include <stdio.h> #include <cstring> const int R = 26; const int N = 250005; //字符串的长度 struct node{ node *next[R], *par; int v; //该节点表示的子串的最大长度,最小长度即为par的最大长度+1,因此可以不用存下来 }nodes[N*2+100], *root; int cnt; //树

  • 求两个字符串的子串(基础算法练习题)

    求两个字符串的子串(基础算法练习) 问题描述: 求两字符串中的最大公共子字符串 并输出长度. 例如"abbcgre","abcgra"中最大子字符串"bcgr" 下面是我的实现: 先找出相对较小的一个字符串,从最大长度比较起,逐渐缩小 比如, abbcgre,abcgra两个字符串,相对长度较小的是abcgra,先看abcgra是否是abbcare的子串, 如果不是,则长度缩小一位 两种可能 abcgr, bcgra渐次比较, length=6

  • 求两个字符串去掉反复字母后所包含字符

    求两个字符串去掉重复字母后所包含字符 要求如下: 如有字符串"AABBCDEFG","EEFGHIJK",希望得到两个字符串合并以后的结果"ABCDEFGHIJK".本来想在网上找一个,没找到合适的,就自己写了一个. /** * 求两个字符串所包含字符的并集 wk 2012.05.19 */ public static String getStringUion(String str1,String str2){ char[] a = str1.t

  • java-写1函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序

    java-写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序. public class CommonSubSequence { /** * 题目:写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序. * 写一个版本算法复杂度O(N^2)和一个O(N) . * * O(N^2):对于a中的每个字符,遍历b中的每个字符,如果相同,则拷贝到新字符串中. * O(N):首先使用b中的字符建立

  • 付出一个字符串所有连续的字串的组合

    给出一个字符串所有连续的字串的组合 可以用stl,链表保存 例如:char *pa="abcd efgh ijkl mn"; 给出所有连续子串的组合,空格也算进去把,例如 cd是 f是 等等 ------解决方案-------------------- strsep + for ------解决方案-------------------- 标准库里有这个函数,貌似是模版 只要每次拿到第一个字符,然后对后面的字符进行分解 如: abc a字符开头 bc cb b字符开头 ac ca c字

  • 基于KMP算法求两个字符串的最大公共子字符串

    在维基百科中对这个算法的介绍是: 在计算机科学中,Knuth-Morris-Pratt 字符串查找算法(常简称为 "KMP算法")可在一个主"文本字符串" S 内查找一个"词" W 的出现位置.此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现,从而避免重新检查先前匹配的字符. 这个算法是由高德纳(Donald Ervin Knuth)和 沃恩·普拉特 在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算

  • 华为OJ: 公共字串计算

    有几个需要注意的地方,一个这道题是不区分大小写的,所以在计算之前对输入的字符串要做小写或者大写的转换. 第二个,思路一定要清晰,先将s1从[i]处开始与s2的[j]开始匹配,不相等则j++直到j等于s2.length()-1,相等,则i++,j++.注意,这里就是i++,即下次重新开始从s[i]开始匹配时,两次i之间的距离可能会超过1.再j那里设置一个计数器计数即可. import java.util.Scanner; public class findMaxSubStringLength {

  • 公共字串计算

    import java.util.Arrays; import java.util.Scanner; public class GetCommonString { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String str1 = scan.next().toLowerCase(); String str2 = scan.next().toLowerCase(); if(str

  • 动态规划求最贵族共字串

    动态规划求最大公共字串 动态规划-----求两个字符串的最大公共字串 package zju; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class SameString { public static void main(String[] args){ String s1=""; String s2="";

  • 利用Trie树求多个字符串编辑距离的更进一步优化

    利用Trie树求多个字符串编辑距离的进一步优化 1.引言 题目的意思应该是:在一个给定的字典中,求与给定的字符串的编辑距离不大于2的所有的单词.原先写过两片关于此问题的文章,那两片篇章文章给出两种解决思路:其一是暴力求解法,这种方法最容易想到.就是将词典中的词一一与给定的字符串计算编辑距离,不大于2的输出,大于2的舍弃,这种方法思路简单但是很费时间.其二根据词典中这些词之间的编辑距离建立一个以单词为节点的Trie树,遍历的时候,通过计算根节点与给定字符串的编辑距离就可以排除掉一部分分支了,然后继

  • 这个字串如何赋值到字符串数组

    这个字串怎么赋值到字符串数组? 这个字串怎么赋值到字符串数组? Dim tData As String tData= "680041680F85612345001100000128571299840000012486161539000001273220491885612345000000000009990000000001125F120F228F004F125F120F228F500000000000020000603E16 " '掉前面的22个字符和后面的4个字符,这些字符是信息头(

  • 算法系列札记6(动态规划—最长公共子序列/串lcs)

    算法系列笔记6(动态规划-最长公共子序列/串lcs) 子序列要求元素顺序一致就可以了,而字串必须是连续的.如ABCBDAB与BDCABA两个字符串,最长公共子序列有BCBA.BDAB和BCAB, 而最长公共字串只有AB和BD<连续>.当然这里的求解只求一个,但通常是这样直接说求最长公共子串,子序列,准确的应该是之一. 最长公共子序列 法一:穷举法 检查字符串x所有字序列,共有2^m个,检查它是否在y字符串中出现,每个需要O(n),时间复杂度为指数级的. 法二:动态规划(DP) 将两个字符串x[

最新文章
  • PPS如何查看付费查看有效期 PPS如何查看付费查看有效期

    有效期指支付一次可享有的影视节目租赁时长,从支付成功的时间开始计算.在节目的播放页及支付过程中均有提示,也可以从账户查询中的影视购买记录中查看.

  • 世界上最脏的内海 世界上最脏的内海

    世界上最脏的内海 地中海是世界上最大的内海,也是世界上最脏的海.平均每年倒人地中海的废水达35亿立方米,固体垃圾1.3亿吨.最为严重的是,邻海18个国家.58个石油港口装卸石油时,给海水带来了严重的石油污染. 地中海作为陆间海,比较平静,加之沿岸海岸线曲折.岛屿众多,拥有许多天然良好的港口,成为沟通三个大陆的交通要道.这样的条件,使地中海从古代开始海上贸易就很繁盛,还曾对古埃及文明.古巴比伦文明.古希腊文明的兴起与更提起过重要作用,成为了古代古埃及文明.古希腊文明.罗马帝国等的摇篮.现在它也是世

  • 面试怎么选择合适的衣服8大通用法则 面试怎么选择合适的衣服8大通用法则

    一项针对招聘经理和人力资源顾问的调查表明雇主确实会把穿着的颜色和面试的性格相关联起来.比如说: 黑色象征着领导力. 红色象征充满力量. 蓝色表明面试者适合在团队中工作. 灰色表明逻辑性和分析头脑. 白色给人一种井井有条的感觉. 绿色,黄色,橙色和创造力相关联. 纽约时装学院的一位造型专家Carol Davision说"从暗示的角度来讲,你的外表可能比你说什么和怎么说能反映出更多信息".而且当面试官第一眼见到你的时候,他首先注意到的是你衣服的颜色. 所以,在准备面试的时候,我们不仅要一遍

  • 网站优化关键在于如何做好自己的网站

    现在有越来越多的人都热衷于网站的优化,一心只想如何使自己的网站有多少的排名,每天拥有多少的流量,自己每个月有多少的收入.天天沉浸在梦想之中.于是乎,每天都开始做自己的网站优化,处处留下自己网站的地址,增加外链.到处宣传自己的网站如何如何的好.可是当你有一天点击进入它的网站之后却发现,不是网站正在建设之中,就是网站的内容根本就不是宣传的那样,在这里你根本就得不到自己想要的东西.却发内容很是垃圾.于是,很多客户停留了短短几秒之后,就选择离开豪不犹豫的关闭窗口,弄得你哭笑不得.还整天吆喝为什么网站没有

  • 一起来卖萌如何删除照片? 一起来卖萌如何删除照片?

    1)首先打开一起来卖萌软件,点击[我的萌],进入界面选择你想要删除的照片,点击[删除]. 2)然后弹出窗口点击[确定]即可删除完毕.

  • Dreamweaver网页制作技巧:使用模板 Dreamweaver网页制作技巧:使用模板

    随着Internet的普及,很多人已经不满足于仅仅上网冲浪,而希望深入地参与其中.现在,拥有自己的Web网站已经成为一种潮流.虽然制作一个简单的网页并不困难,但是制作出超凡脱俗的网站就不那么容易了,因此我们特意为大家准备了最新网站设计软件Dreamweaver MX 2004的系列教程,希望对大家有所帮助. 通常在一个网站中会有几十甚至几百个风格基本相似的页面,如果每次都重新设定网 页结构以及相同栏目下的导航条.各类图标就显得非常麻烦,不过我们可以借助Dreamweaver MX 2004的模板

  • 关于道歉的qq表情大全_好玩的搞笑表情包下载 关于道歉的qq表情大全_好玩的搞笑表情包下载

    关于道歉的qq表情大全_好玩的搞笑表情包下载

  • 酷派锋尚pro 无法播放视频文件怎么办? 酷派锋尚pro 无法播放视频文件怎么办?

    酷派锋尚pro 无法播放视频文件怎么办?下面本站就给大家讲解: 在播放视频之前要安装播放软件,我建议安装QQ影音,请确认需要播放或者查看的文件是否与手机兼容,Android操作系统不能支持全部格式的文件,可以通过安装第三方工具来增加Android操作系统所支持的文件格式.

  • 暴风影音力推“环绕声” 高调姿态惹争议 暴风影音力推“环绕声” 高调姿态惹争议

    近日,暴风影音发布新功能"环绕声".据悉,暴风环绕声采用了HRTF技术,意为增强声音的纵深感.临场感和空间感. 据暴风影音产品总监王干介绍:"暴风的环绕声功能简单说,就是将音频信号中各声源的方向再现.开启该功能后,不仅能感受到来自前.后.左.右的立体声源,甚至感觉四周都被这些声源所产生的空间声场所包围,从而为用户营造出一种置身于影剧院的音响效果." 他还透露,由于暴风影音"环绕声"优秀的声音效果,打动了德国百年知名耳机品牌森海塞尔,双方携手为推动

  • 通过rowid逻辑并行抽取数据

    通过rowid逻辑并行抽取数据 在我们迁移数据,或者进行同步数据的时候,对于应用变更频繁的表进行抽取数据,经常会碰到oracle需要读取回滚段,会导致很慢,有时候甚至会报ora01555错误, 比如我们有个表比较大是40G左右,就是一个月的按月分区数据,这个时候如果想尽快抽取数据到另外一个库,有几种方法: 方法1: www.2cto.com 大家都知道的使用append,然后不写日志,parallel抽取方式: 代码类似如下: [sql] alter session enable paralle

热门推荐
  • 万圣节的鬼怪有哪些 万圣节的鬼怪有哪些 [南瓜灯] 南瓜是万圣节的代表,在脑袋上套个南瓜吧,记得留几个洞. [幽灵] 幽灵的传说遍及全世界,鬼怪的节日自然也少不了它的出现. [僵尸] 一脸煞白或是满面挂彩,僵尸的形象随你想象. [吸血鬼] 优雅.高贵而又冷酷的血族历来都是神秘午夜故事中的常客. [巫婆] 黑猫.扫把.魔法帽--法力无边,但要当心脸上的皱纹哦. [科学怪人] 科幻史上的经典科学怪人,如今也经常现身于万圣节中. [精灵] 每个人心中都有自己的精灵,你想象的精灵是什么模样? [半人马] 半人马的来源在希腊神话中说法不一,于是
  • 要如何杜绝卫浴装修遗憾 要如何杜绝卫浴装修遗憾 几乎每个装修完的家庭都会留有一些遗憾,或是设计时考虑不周,或是装修时的疏忽而留下"后遗症".特别是卫生间装修容易留下遗憾.那要如何杜绝卫浴装修遗憾呢?香香小编来为您支招吧! 一.台盘装修三大遗憾 解决问题有妙招 洗脸台盆要选择"通体"的不可选择仅有一层表面胶壳的那种,因仅有表面胶壳的台面一经破损即无法修复.(要检验台面是否为"通体",可用灯光从背面近距离照射,可透光的才是"通体"的台面).另外台面和洗脸盆接缝处必须打填缝剂,防
  • 柴米油盐酱醋茶 柴米油盐酱醋茶 柴 柴生火,卖火柴的小女孩擦亮火柴 看到的是希望,火柴灭了希望散了 爱情,有时候也是需要互相的取暖 米 有些人选择爱情,有些人选择了米 不能把爱情和米跟鱼和熊掌做比较 如果一定要在爱情和米之间做选择 ‑‑ 我坚信因为你,我可以俩者都兼得 油 从超市买回的花生油 厨房里飘的油香都是那花生的味道 每天一直都萦绕着思念和等待 盐 把盐放进菜里,才能显出菜的味道 盐用的适当,适当了才能够合口味 合口味了的关键是心里有一份宽容 宽容的关键是有爱,爱是盐的精华 酱 在南方的冬天空气既潮湿而且阴冷 灯光下,心
  • 中看不中用 网友称高铁车厢WiFi无法连接 中看不中用 网友称高铁车厢WiFi无法连接 "我在武汉到北京的高铁上,车上能搜到无线宽带网了--"昨天,博友"@Babymimi"惊喜地发现,高铁车厢有无线宽带,但没高兴多久,她就发现,这个接入点根本连不上,是"中看不中用". 记者昨采访了解到,武汉至北京.广州.深圳高铁车厢里,能搜到若干个以"CRH"开头的未加密Wi-Fi热点信号,可是尝试登录无法连接,上不了网. 乘客问列车员:这是钓鱼网站? 昨天中午,在武汉火车站准备上客的一趟武汉-广州高铁上,记者打开iPad平板
  • 你是不是爱情 或只是陪着我旅行 你是不是爱情 或只是陪着我旅行 ①当我唱起这首歌,眼泪不听话了 歌词里的故事与现实渐渐重叠,像一场很早就上演的老旧默片. 我突然很想拥有某个人然后霸道的拉他去各个小巷弄口. 我下错了车站然后又与谁相撞互道对不起时的不经意一瞥. 我在日记本上写满属于我和谁的名字. 白色衬衣.洗得发白的蓝色牛仔裤.单车. 我和你.这是不是爱情. ②我们曾经说好要一起去看海 我带着所有去看海, 没有春暖花开的温暖,亦没有给我心灵带来触动, 不同面孔不同类型的人,脸上的表情各自出神. 会不会有人和我一样,也是因为"春暖花开" 然后只身来到这
  • itudou怎么下载视频? itudou怎么下载视频? itudou怎么下载视频?提到itudou,可能很多网友都不是很熟悉,其实,itudou是一款土豆网官方的视频下载跟上传的客户端.那么,itudou怎么下载视频呢?在今天的itudou使用教程中,我们就具体来讲解一下这个itudou的使用方法! itudou 安装好软件,打开itudou,选择下载栏目,然后进行新建下载项目 itudou 到土豆网站去物色你喜欢的视频,然后复制网页的地址,然后将网页的地址粘贴到,新建的下载项目上,点击:确定. 下载完毕,打开下载文件夹,就可以查找到下载视频!