[字符串处理算法]求最长公共子串的算法设计及C代码实现。例如，如果输入字符串是“abcdef”和“fecdba”，那么这两个字符串的最长公共子串就是“cd”。2.算法设计我们可以先找到两个字符串中第一个相等的字符，然后向后移动比较对应位置的字符是否相等。即如果字符串1为“1234abcd”，字符串2为“abd”，则先查找字符串1中的第5个字符“a”等于字符串2中的第1个字符“a”，然后查找第6个字符字符串1中的“b”等于字符串2中的第二个字符“b”，然后发现字符串1中的第七个字符“c”等于字符串2中的第三个字符“d”不相等，比较到此结束。也就是说，字符串1和字符串2的最长公共子串是“ab”。三、特殊过程注意事项在编写程序的过程中，我们需要考虑输入字符串的长度和格式，如：1、如果两个输入字符串中有一个包含汉字，则程序直接返回，不进行后续操作程序。2.如果输入的两个字符串中有一个包含空格，则程序获取空格前的字符串进行后续操作。4.程序代码/***************************************************************************Copyright(C)2016,ZhouZhaoxion.**文件名：GetLCS.c*文件ID：无*内容概要：求两个字符串的最长公共子串*其他说明：例如“abcdef”和“bcf”的最长公共子串是“bc”*当前版本：V1.0*作者：周兆雄*完成日期：20160322********************************************************************************/#include#include#include//重新定义数据类型typedefsignedcharINT8;typedefintINT32;typedefunsignedintUINT32;//函数声明voidGetLCSOfTwoStr(INT8*pszInputStr1,INT8*pszInputStr2);/*******************************************************************************函数说明：主函数*输入参数：无*输出参数：无*返回值：0-执行成功其他-执行失败*其他说明：无*修改日期版本号修改按修改内容*--------------------------------------------------------------------*20160322V1.0ZhouZhaoxiongCreated********************************************************************************/INT32main(){INT8szInputStr1[100]={0};INT8szInputStr2[100]={0};UINT32iPosFlag=0;printf("Pleaseinputstring1:\n");scanf("%s",szInputStr1);printf("InputStr1=%s\n",szInputStr1);printf("请输入strng2:\n");scanf("%s",szInputStr2);printf("InputStr2=%s\n",szInputStr2);//先判断是否有汉字for(iPosFlag=0;iPosFlag0){printf("%s和%s之间的最长公共子串为：%s，其长度为：%d\n",pszInputStr1,pszInputStr2,szLCS,iLCSLen);}else{printf("%sand%shavenocommonsubstring!\n",pszInputStr1,pszInputStr2);}}5.程序测试我们将编写好的程序“GetLCS.c”上传到Linux机器上，使用““gcc-g-oGetLCSGetLCS.c”命令编译程序，生成“GetLCS”文件，对程序进行详细测试。1、当输入字符串1为“abcdef”，字符串2为“hijkabm”时，程序运行如下：22、当输入字符串1为“1234!@#”，字符串2为“5678!@#1”时，程序运行如下：Pleaseinputstring1:1234!@#InputStr1=1234!@#Pleaseinputstring2:5678!@#1InputStr2=5678!@#11234!@#和5678!@#1的最长公共子串为：!@#，其长度为：33。输入串1为“123hello”，串2为“123”，程序运行如下：Pleaseinputstring1:123HelloInputStr1=123HelloPleaseinputstring2:123InputStr2=123123你好有汉字，请检查！4、当输入字符串1为“123abc”，字符串2为“abdef”时，程序运行如下：Pleaseinputstring1:123abcInputStr1=123abcPleaseinputstring2:abdefInputStr2=abd123abcandabd最长公共子串为：ab，其长度是：25.当输入字符串1为“abcdef”，字符串2为“123456”时，程序运行如下：6.需求扩展基于本文的需求和流程，我们可以考虑对需求进行如下扩展：1.如果两个字符串存在一个以上的最长公共子串，则必须输出，即如果字符串1为“1234abcd”，字符串2为“abd12”，则程序输入的最长公共子串为“12”和“ab”2.输入的字符串中没有不能出现汉字的限制，即如果字符串1是“We123”，字符串2是“we”，那么最长公共子串就是“us”。【本文为专栏作家周兆雄原创文章，作者微信公众号：周氏逻辑（logiczhou）】点此阅读更多本作者好文
