【字符串处理算法】获取最长公共子串的算法设计及C代码实现

今天讲讲获取最长公共子串的算法设计及C代码实现的知识。

一、需求描述

输入两个字符串，编写程序获取这两个字符串的***个最长公共子串。

例如，输入的字符串为“abcdef”和“fecdba”，那么这两个字符串的***个最长公共子串为“cd”。

二、算法设计

我们可以首先寻找两个字符串中的***个相等的字符，然后分别向后移动来比较对应位置的字符是否相等。

即如果字符串1为“1234abcd”，字符串2为“abd”，那么首先发现字符串1中的第五个字符“a”与字符串2中的***个字符“a”相等，接着字符串1中的第六个字符“b”与字符串2中的第二个字符“b”相等，再接着发现字符串1中的第七个字符“c”与字符串2中的第三个字符“d”不相等，此时比较结束。也就是说字符串1和字符串2的最长公共子串为“ab”。

三、特殊流程考虑

在编写程序的过程中，我们要对输入的字符串的长度及格式多做考虑，如：

1.如果输入的两个字符串之一含有中文字符，那么程序直接返回而不执行后续流程。

2.如果输入的两个字符串之一含有空格，那么程序获取空格之前的字符串进行后续操作。

四、程序代码

/**********************************************************************
*版权所有(C)2016,ZhouZhaoxiong。
*
*文件名称：GetLCS.c
*文件标识：无
*内容摘要：寻找两个字符串的最长公共子串
*其它说明：例如,"abcdef"和"bcf"的最长公共子串是"bc"
*当前版本：V1.0
*作者：ZhouZhaoxiong
*完成日期：20160322
*
**********************************************************************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//重新定义数据类型
typedefsignedcharINT8;
typedefintINT32;
typedefunsignedintUINT32;
//函数声明
voidGetLCSOfTwoStr(INT8*pszInputStr1,INT8*pszInputStr2);
/**********************************************************************
*功能描述：主函数
*输入参数：无
*输出参数：无
*返回值：0-执行成功其它-执行失败
*其它说明：无
*修改日期版本号修改人修改内容
*---------------------------------------------------------------------
*20160322V1.0ZhouZhaoxiong创建
***********************************************************************/
INT32main()
{
INT8szInputStr1[100]={0};
INT8szInputStr2[100]={0};
UINT32iPosFlag=0;
printf("Pleaseinputstring1:\n");
scanf("%s",szInputStr1);
printf("InputStr1=%s\n",szInputStr1);
printf("Pleaseinputstring2:\n");
scanf("%s",szInputStr2);
printf("InputStr2=%s\n",szInputStr2);
//先判断是否有中文字符
for(iPosFlag=0;iPosFlag<strlen(szInputStr1);iPosFlag++)
{
if(szInputStr1[iPosFlag]<0)//小于0则表示含有中文字符
{
printf("%shasChinesecharacter,pleasecheck!\n",szInputStr1);
return-1;
}
}
for(iPosFlag=0;iPosFlag<strlen(szInputStr2);iPosFlag++)
{
if(szInputStr2[iPosFlag]<0)//小于0则表示含有中文字符
{
printf("%shasChinesecharacter,pleasecheck!\n",szInputStr2);
return-1;
}
}
//再调用函数获取两个字符串的最长公共子串
GetLCSOfTwoStr(szInputStr1,szInputStr2);
return0;
}
/**********************************************************************
*功能描述：获取两个字符串的最长公共子串
*输入参数：pszInputStr1-输入字符串1
pszInputStr2-输入字符串2
*输出参数：无
*返回值：无
*其它说明：无
*修改日期版本号修改人修改内容
*---------------------------------------------------------------------
*20160322V1.0ZhouZhaoxiong创建
***********************************************************************/
voidGetLCSOfTwoStr(INT8*pszInputStr1,INT8*pszInputStr2)
{
UINT32iInnerLoopFlag=0;
UINT32iOutterLoopFlag=0;
UINT32iPosFlag=0;
UINT32iLCSLen=0;
INT32iStartPos=-1;
INT8szLCS[100]={0};
if(pszInputStr1==NULL||pszInputStr2==NULL)
{
return;
}
for(iOutterLoopFlag=0;iOutterLoopFlag<strlen(pszInputStr1);iOutterLoopFlag++)
{
for(iInnerLoopFlag=0;iInnerLoopFlag<strlen(pszInputStr2);iInnerLoopFlag++)
{
if(pszInputStr1[iOutterLoopFlag]==pszInputStr2[iInnerLoopFlag])
{
for(iPosFlag=1;pszInputStr1[iOutterLoopFlag+iPosFlag]!='\0';iPosFlag++)
{
if(pszInputStr1[iOutterLoopFlag+iPosFlag]!=pszInputStr2[iInnerLoopFlag+iPosFlag])//遇到不相等的字符,则退出比较
{
break;
}
}
if(iLCSLen<iPosFlag)
{
iLCSLen=iPosFlag;
iStartPos=iOutterLoopFlag;
}
}
}
}
if(iStartPos==-1)
{
memset(szLCS,0x00,sizeof(szLCS));
}
else
{
memcpy(szLCS,&pszInputStr1[iStartPos],iLCSLen);
}
if(iLCSLen>0)
{
printf("%s和%s的最长公共子串是:%s,其长度是:%d\n",pszInputStr1,pszInputStr2,szLCS,iLCSLen);
}
else
{
printf("%s和%s无公共子串!\n",pszInputStr1,pszInputStr2);
}
}

五、程序测试

我们将编写好的程序“GetLCS.c”上传到Linux机器，并使用“gcc -g -o GetLCS GetLCS.c”命令对该程序进行编译，生成“GetLCS”文件。下面对程序进行详细的测试。

1.输入字符串1为“abcdef”，字符串2为“hijkabm”时，程序运行情况如下：

Pleaseinputstring1:
abcdef
InputStr1=abcdef
Pleaseinputstring2:
hijkabm
InputStr2=hijkabm
abcdef和hijkabm的最长公共子串是:ab,其长度是:2

2.输入字符串1为“1234!@#”，字符串2为“5678!@#1”时，程序运行情况如下：

Pleaseinputstring1:
1234!@#
InputStr1=1234!@#
Pleaseinputstring2:
5678!@#1
InputStr2=5678!@#1
1234!@#和5678!@#1的最长公共子串是:!@#,其长度是:3

3.输入字符串1为“123你们好”，字符串2为“123”时，程序运行情况如下：

Pleaseinputstring1:
123你们好
InputStr1=123你们好
Pleaseinputstring2:
123
InputStr2=123
123你们好hasChinesecharacter,pleasecheck!

4.输入字符串1为“123abc”，字符串2为“abd ef”时，程序运行情况如下：

Pleaseinputstring1:
123abc
InputStr1=123abc
Pleaseinputstring2:
abdef
InputStr2=abd
123abc和abd的最长公共子串是:ab,其长度是:2

5.输入字符串1为“abcdef”，字符串2为“123456”时，程序运行情况如下：

Pleaseinputstring1:
abcdef
InputStr1=abcdef
Pleaseinputstring2:
123456
InputStr2=123456
abcdef和123456无公共子串!

六、需求扩展

基于本文中的需求和程序，我们可考虑对需求进行以下扩展：

1.如果两个字符串有多于一个最长公共子串，则都要将它们输出，即如果字符串1为“1234abcd”，字符串2为“abd12”，那么程序输入的最长公共子串为“12”和“ab”。

2.不限制输入字符串中不能出现中文字符，即如果字符串1为“我们123”，字符串2为“我们”，那么最长公共子串为“我们”。

【本文是清一色专栏作者周兆熊的原创文章，作者微信公众号：周氏逻辑(logiczhou)】

戳这里，看该作者更多好文