算法仿真|公共字符串长度问题求解——华为OJ题目

一、问题描述
以下是题目的描述
题目标题:
计算两个字符串的最大公共字串的长度,字符不区分大小写
详细描述:
接口说明
原型:
int getCommonStrLength(char * pFirstStr, char * pSecondStr);
输入参数:
char * pFirstStr //第一个字符串
char * pSecondStr//第二个字符串

二、问题分析
两个字符串的公共字符串问题的求解,可以采用一种比较简单的方法,如果要提高算法效率,可以对一些方面进行优化。分别定义两个指针指向两个字符串首字符,开始搜索从这两个字符开始得到的最长公共字符串。搜索字符串时候,遇到不相同的字符即停止搜索。然后后移一位第二个字符串的指针,再重复上述搜索过程,知道第二个字符串的指针移动到最后一个字符时候,就后移一位第一个字符串的指针,这样等到两个指针均移动到对应字符串的最后一个字符时候,就可以得到全局的最长公共字符串。
三、源代码与分析
以下代码中int getCommonStrLength(char * pFirstStr, char * pSecondStr)函数即为求解最长公共字符串长度的函数。该函数中,最外层的两个for循环对应字符串指针后移操作,内层的while循环为在匹配到相同的字符时向后继续匹配,直到遇到第一个不匹配的字符即停止。
#include "stdio.h"
#include "string.h"
int getCommonStrLength(char * pFirstStr, char * pSecondStr);
void main()
{
int len1,len2;
char a[257],b[257];
scanf("%s %s",a,b);
printf("%d\n",getCommonStrLength(a,b));


}


int getCommonStrLength(char * pFirstStr, char * pSecondStr)
{
int len1=0,len2=0,i=0,j=0,k=0,num=0,maxnum=0;
len1=strlen(pFirstStr);
len2=strlen(pSecondStr);
for(i=0; i{
for (j=0; j{
if(pFirstStr[i]==pSecondStr[j]||(pFirstStr[i]-pSecondStr[j])==32||(pFirstStr[i]-pSecondStr[j])==-32)
{
num=1;
k=1;
while ((j+k){
if(pFirstStr[i+k]==pSecondStr[j+k]||(pFirstStr[i+k]-pSecondStr[j+k])==32||(pFirstStr[i+k]-pSecondStr[j+k])==-32)
{
num++;
k++;
}
else
break;
}
}
if (num>maxnum)
{
maxnum=num;
}
}

}
return maxnum;
}

四、程序运行结果
算法仿真|公共字符串长度问题求解——华为OJ题目
文章图片


【算法仿真|公共字符串长度问题求解——华为OJ题目】图1 程序运行结果图

    推荐阅读