算法仿真|公共字符串长度问题求解——华为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题目】图1 程序运行结果图
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- SpringBoot调用公共模块的自定义注解失效的解决
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）