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

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

日期: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[

最新文章
  • 求推荐 Mac 上适合程序员的图片编辑软件

    好吧,"适合程序员"这个描述可能不太恰当(甚至会有人喷),但是我真的一时没想到怎么总结这种需求- 我希望找一个适合"程序员",而不是"摄影师"或者"设计师"的图片编辑软件,典型的需求包括: 把第(x1,y1)到(x2,y2)的图像截出来 把两个图片叠起来,准确的放置位置(x,y) resize 至(w,h),甚至选择 interpolation 方式( nearest/linear/etc ) 反色/ split rgb /转

  • AdBlock如何屏蔽页面上某个特定文字?

    现在常用的一个页面图片压缩的厉害,观察代码发现其图片链接后面带了一个"/small"的参数,我想将其屏蔽掉这样直接请求清晰的图片,试了一下无果,求教各位~ 比如<img src="http://abc.com/img.jpg/small" /> --cut-- kurtrossel在2013-01-25 21:05:0回答到: ad实现不了这功能 除非你直接请求原图 我感觉如此 toothpaste在2013-01-25 21:20:3回答到: 这个需求

  • 三年级我爱读书手抄报 三年级我爱读书手抄报

    三年级我爱读书手抄报图片: 描写读书的句子 1.书是灯,读书照亮了前面的路;书是桥,读书接通了彼此的岸;书是帆,读书推动了人生的船.读书是一门人生的艺术,因为读书,人生才更精彩! 2.读书可以充实我们的思想,可以丰富我们的情感,可以教给我们本领,可以纠正我们的过失,在书籍中,你可以真切地感受到生活原本是如此地美好! 3.读书可供消遣,可供装饰,也可供增长才干.为消遣而读书,常见于独处退居之时;为装饰而读书,多用于高谈阔论之中;为增长才干而读书,主要在于对事物的判断和处理. 4.对喜欢阅读的人来说

  • 工具类的APP应该怎样运营,从这四个点切入 工具类的APP应该怎样运营,从这四个点切入

    前两天,有一位读者给我试用了一下他们的工具型App,而很巧的是,上周也有个读者希望我来聊聊工具型产品的运营. 那今天就来做个不深入的讨论. 一.切入点要准运营初始化 首先要明确,无论什么产品,在开始运营前都会讨论切入点. 切入点之所以关键,是因为切入点和以下因素相关: 用户属性:谁是工具的目标用户?用户需求:这些用户的需求是什么?用户触达:哪里可以找到这些用户?用户契合:用户有可能使用我的产品吗?用户获取:如何让他们真的用我的产品?用户活跃:如何让他们按照预期的频次使用我的产品?用户付费:如何让

  • Photoshop打造玻璃效果技巧 Photoshop打造玻璃效果技巧

    制作玻璃效果的中国印 最终效果图 1.新建一个文件,打开标志图片如图01所示,使用工具箱中的"魔棒工具"选择标志,将其拖拽到文件中,自动生成图层1,并将其填充黑色,效果如图02所示. 图01 图02 2.按Ctrl键单击图层1,调出标志选区,切换到通道面板,在面板底部单击"将选区存储为通道"按钮,将选区保存为通道,如图03所示. 图03

  • 美好的爱情句子 美好的爱情句子

    1:于万千的人群中,于无际涯的时光里,一个人没有早一步,也没有晚一步,恰巧奔赴到你的人生中来,有几分命运,也有几分注定.轻颦回眸,流年里,若有一个人,在你的生命中烟花般绚烂过,流星般璀璨过,纵使隔了沧海桑田,却可在文字里想念,可在记忆里沉香,这,又何尝不是一种温暖? 2:于花季青春里与你邂逅,我不知道是劫是缘,站在三生石边聆听那世花开,醉里经年,挑灯吟月,纤指笙歌,犹记歌中繁华梦. 3:也许所有的爱,都是那么的真实,但有时还那么的让人受苦不堪.真的,我就是在痛苦的煎熬中,那么的死心塌地的爱着你,

  • 描写河流的句子

    1.从前,有一个美丽迷人的小村庄.村庄里有一条清澈的小河,小河里鱼虾成群.住在村庄里的人们每天都要到小河里来挑水. 2.秋天,河边的树木都开始枯萎了,树上的叶儿由青转黄,飘飘悠悠地从树上飘落到河面上,连树上的野果子也不甘寂寞,也随着叶子一起落了下来,一起装扮着这诗情画意的小河.我突然想起我姥姥做的果汁,这小河也如同我姥姥做的果汁,使人回味无穷! 3.小河是顽皮的,流水潺潺,水儿轻轻流动着,哗哗的河水不断顽皮的流出,翻腾着喜悦的波纹;小河是那么温柔,闭上你的眼睛坐在河边,静听小河的歌声.那是温柔的

  • 传奇乐队Beyond代言?金立12月21日将推“超级续航” M5 Plus 传奇乐队Beyond代言?金立12月21日将推“超级续航” M5 Plus

    近日,国产手机厂商金立在其官方微博发布了一张预热海报,海报透露金立即将于本月21号发布旗舰配置的新品.更让人期待的是,预热海报上出现了疑似Beyond乐队成员的人物形象及"海阔天空"四个大字,令人浮想联翩. 通过海报可以看出,金立M5Plus上市发布会确认将于12月21日召开.而海报中间的两个人物颇似为Beyond乐队成员,再加上<海阔天空>又是Beyond成名曲,莫非会有Beyond重聚,为金立M5Plus发布会助阵?又或是金立将签下Beyond作为品牌代言人?如此预热神

  • 嘉兴种福堂

    是南宋王渊子孙的宅院. 相传王渊是宋高宗赵构南渡时,护驾随行到江南的.元朝末年,其子孙为了躲避战乱而定居嘉兴,后来,又移居到了西塘镇. 种福堂建于清朝顺康年间,共有八进,沿河临街进门.第一进是"门厅":第二进是"桥厅":第三厅是"种福堂",厅堂中央悬挂着海宁陈邦彦题写的"种福堂"匾额.由一条长弄连通整个宅院前后.

  • Windows 10自定义右键菜单中应用程序教程 Windows 10自定义右键菜单中应用程序教程

    Windows 10系统如何在右键菜单中自定义添加应用程序?我们在安装杀毒软件或电脑助手时都会发现安装好了在右击菜单中会看到它们的身影了,下面我们来看看如何在win10系统中自己定义右键菜单中应用程序了,具体和一聚教程小编来看看吧. 1.我们在win10电脑我们按下键盘上的 Win + R 组合键,然后在打开"运行"窗口,我们只需要填写"regedit.exe"打开注册表,细节如下图所示: 2.在进入到注册表下面我们只需要定位到"HKEY_CLASSES_

热门推荐
  • 不同护肤品不同保鲜期 不同护肤品不同保鲜期 对于你的护肤品你知道它的保鲜期吗?目前,国际大品牌的包装上面都有一个开封的小圆盒标志,上面写着6M.12M之类的字母,表示开封后产品能够保证在多少个月以内新鲜有效.每个美容产品都有属于自己的保质期,所以请仔细阅读. 乳霜:开封后应在1年内用完,但如直接用手从瓶中取用,会加速变质. 乳液:乳状乳液也可使用1年,水状乳液则变质较快,一旦出现异味就表示新鲜不再. 眼霜:最多可使用1年,如出现油乳分离或产生异味,则可能意味着眼霜中的油分已变质,应早放弃.编辑提示:眼霜也是高危产品,使用时不小心可能入眼,
  • 微信聊天记录如何导出备份到电脑? 微信聊天记录如何导出备份到电脑? 图1 [聊天记录备份流程] A.在电脑管家工具箱中找到"微信聊天备份"功能,打开后可选择USB连接或者WIFI连接两种方式. 图2 B.选择要备份的聊天记录后,开始备份. 图3 C.安全加密备份成功.之后需要时可以随时将备份到电脑上的聊天记录再恢复到手机. 图4 D.手机上需确认授权,开始备份. 图5 [微信聊天记录备份]两个特色 1. 本地无限期存储,让备份过程飞起来. 2. 无线WIFI链接,打破传统USB链接方式的局限,更便捷.
  • 怎样选购真皮沙发? 怎样选购真皮沙发? 一.海绵作为真皮沙发中不可或缺的部分,在选购真皮沙发的时候也要问清楚,一般海绵分为高弹.高弹超软.中弹几种,一般中弹用做靠背和扶手.高弹用作座位,高档的真皮沙发都是配以高弹的海绵,在购选沙发的时候不仅要问,还要自己试试柔软度. 二.选购真皮沙发其实不光光是选皮,木架也是不容忽视的,好沙发的木架一般都是由方木钉在板子上,这种就比较牢固,而且不一般行,劣质的沙发因为木架不好,很容易就出现一些凹凸面了,所以选择沙发的时候要注意这一点. 三.真皮沙发的皮质主要有猪皮.马皮.驴皮.牛皮等几种,其他材质的皮
  • 日久见人心,谁会在乎你 日久见人心,谁会在乎你 不摔那么一跤, 就不知道有谁愿意停下来等你. 不有求于人, 就不会知道谁会在关键时刻关心你. 有段时间你突然和一些人关系很好, 以为彼此可以成为真正的朋友, 然而他却会逐渐淡漠出你的记忆. 有的时候你会不得不跟某人天天黏在一起. 可是突然有一天, 他会一言不发地悄然离去. 我花了太久的时间才学会, 和谁都不要熟得太快, 不要对谁都掏心掏肺, 因为不是每个人都真的希望了解你 相互成为真正意义上的朋友. 不要以为自己在谁那里都吃得开, 有的人就是看不惯你顺利, 日久见人心. 朋友就是那些看到 你全部
  • 粗粮怎么吃才健康 粗粮怎么吃才健康 粗粮怎么吃才健康 按照中国营养学会建议,在全天250克-400克主食中,粗杂粮占50克-100克.正常人吃粗粮以天天一次为宜,高血压.高血脂.糖尿病患者则可以安排一天两次.吃粗粮的时间以正午为佳. 过多食用粗粮会拔苗助长 人类的饮食经历了由"粗"到"细"的转变,如今又开始了由"细"到"粗"的折返,以至于粗粮的价格高于细粮.切实其实,粗粮中含有大量的纤维素,有助于促进肠蠕动,保持大便通行,对于预防心脑血管疾病和肠癌等有一定的好处
  • 微信路由器怎么设置? 微信路由器怎么设置? 1.首先,我们将电脑用网线连接至微信路由器LAN端口. 2.然后打开电脑的网络连接 3.在本地连接上右键,选择属性. 在弹出来的属性窗口双击 Internet 协议.然后将电脑ip由自动获取改为手动设置,输入本地ip为 192.168.1.8网关ip为 192.168.1.1DNS设置为 8.8.8.8保存即可. 4.然后打开浏览器,访问192.168.1.1默认账号密码是 admin admin这个密码过于简单,在配置好路由器之后,需要更改密码,以防被用户修改设置. 5.路由器界面,功能很强大
  • 电脑版本qq更换皮肤操作方法 电脑版本qq更换皮肤操作方法 qq皮肤分为收费与免费皮肤了,我们这里介绍的是免费皮肤的更换了,如果各位不知道的话就可以同小编一起来看看电脑版本qq更换皮肤操作方法,希望文章能给大家带来帮助. 1.在QQ登录界面我们点击上面的衣服图标,如下图所示,即红框内衣服图标 2.如我们在进入到QQ皮肤管理界面,你会发现蓝框内带VIP字样的皮肤只能是会员才能使用 在此各位根据自己的情况来选择皮肤吧. 3.找到自己喜欢的皮肤点击就可以就可以更换使用此皮肤了. 4.换好后你的qq主题皮肤界面就更换了,如果没有更新我们可以重启QQ,如果重启QQ