文档章节

找出两个字符串中最大的公共子串的简单实现

Endroid
 Endroid
发布于 2013/10/06 09:46
字数 218
阅读 6733
收藏 8
#include <stdio.h>
#include <string.h>
#include <assert.h>
// 找出两个字符串中最长的公共子串(如果存在多个 , 返回第一个)
// 参数:str1  		字符串1
//    str2		字符串2
//    maxSubStr    找到的最大子串
void findMaxSubstr(const char *str1 , const char *str2 , char *maxSubstr){
	assert((str1!=NULL)&&(str2!=NULL));
	assert(maxSubstr!=NULL);

	int maxPos=-1;
	int maxLen=0;	//相同字符串的最大长度
	
	// 穷举
	for(unsigned int i=0; i<strlen(str1); i++)
	{
		for(unsigned int j=0; j<strlen(str2); j++)
		{
			if(str1[i] == str2[j])	//发现相同的字母
			{
				// 继续比较后面的是否也相同
				for(int k=1; (str1[i+k]==str2[j+k])&&(str1[i+k]!='\0'); k++)
					;	
				if(k>maxLen)	// 是否为目前最长字符串
				{
					maxPos=i;	// 起始位置
					maxLen=k;	// 长度
				}
			}
		}
	}
	
	if(maxPos==-1)
	{
		maxSubstr[0]='\0';
	}
	else
	{
		memcpy(maxSubstr , str1+maxPos , maxLen);
		maxSubstr[maxLen]='\0';
	}
}

int main()
{	
	char substr[20];
	findMaxSubstr("dddabd123456abcdefeeeee" , "234dddabcdegeeee" , substr);	
	printf("%s\n",substr);
	return 0;	
}

© 著作权归作者所有

上一篇: char 转成 string
下一篇: 快速排序
Endroid
粉丝 8
博文 46
码字总数 68781
作品 0
深圳
程序员
私信 提问
最长公共前缀

原题   Write a function to find the longest common prefix string amongst an array of strings. 题目大意   写一个函数找出一个字串所数组中的最长的公共前缀。 解题思路   第一步...

一贱书生
2016/12/12
10
0
[算法总结] 13 道题搞定 BAT 面试——字符串

本文首发于我的个人博客:尾尾部落 1. KMP 算法 谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把...

繁著
2018/09/05
0
0
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0
串的应用与kmp算法讲解--学习笔记

串的应用与kmp算法讲解 1. 写作目的 平时学习总结的学习笔记,方便自己理解加深印象。同时希望可以帮到正在学习这方面知识的同学,可以相互学习。新手上路请多关照,如果问题还请不吝赐教。 ...

huangzhuyun
06/06
0
0
【DSAA】Longest Palindromic Substring

最近刷LeetCode遇到一个比较有意思的题目(Longest Palindromic Substring),求一个字符串的最大回文子串。题目本身并不难,但需要理清思路才好理解,借此文记录下。 题目 Given a string s...

jiantao88
2018/01/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

UiPath announced the acquisition of StepShot and ProcessGold

In 2018, an estimated 1.8 billion consumers worldwide bought goods online, generating e-retail sales of $2.8 trillion. By 2021, this figure is expected t0 reach $4.8 trillion. Y......

巧克夹心
6分钟前
5
0
好程序员Java教程分享Java中this的几种用法

  好程序员Java教程分享Java中this的几种用法,this关键字必须放在非静态方法里面   this关键字代表自身,在程序中主要的使用用途有以下几个方面:   ?使用this关键字引用成员变量   ...

好程序员官网
11分钟前
3
0
ElasticsearchRepository

关键字 使用示例 等同于的ES查询 And findByNameAndPrice {“bool” : {“must” : [ {“field” : {“name” : “?”}}, {“field” : {“price” : “?”}} ]}} Or findByNameOrPrice {“b...

少年已不再年少
18分钟前
3
0
python学习13.04:什么是位置参数,Python位置参数

位置参数,有时也称必备参数,指的是必须按照正确的顺序将实际参数传到函数中,换句话说,调用函数时传入实际参数的数量和位置都必须和定义函数时保持一致。 实参和形参数量必须一致 在调用函...

太空堡垒185
22分钟前
3
0
mysql索引

一、什么是索引?为什么要建立索引? 索引用于快速找出在某个列中有一特定值的行,不使用索引,MySQL必须从第一条记录开始读完整个表,直到找出相关的行,表越大,查询数据所花费的时间就越多...

蜗牛女孩
31分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部