华为机试题75-公共子串计算

描述

给定两个只包含小写字母的字符串,计算两个字符串的最大公共子串的长度。

注:子串的定义指一个字符串删掉其部分前缀和后缀(也可以不删)后形成的字符串。

数据范围:字符串长度:1≤s≤150

进阶:时间复杂度:O(n^3) ,空间复杂度:O(n)

输入描述:

输入两个只包含小写字母的字符串

输出描述:

输出一个整数,代表最大公共子串的长度

示例1

输入:

asdfas
werasdfaswer

输出:

6


解题思路:

直接暴力求解了,没用动态规划。

先将两个字符串的短串和长串区分开来,然后从短串的长度开始找子串(此时为原短字符串),遍历长串在这个长度下的子串,查看是否有匹配的子串,如果有,就可以终止查找,否则将短串的子串长度减1,找出这个长度下的短串子串和长串子串,若有就终止,没有的话搜索子串长度再减1,继续查找。代码如下:

#include <stdio.h>
#include <string.h>
#define    N    150
int main()
{
    char str1[N],str2[N],son1[N],son2[N];
    scanf("%s%s",str1,str2);
    int len1=strlen(str1),len2=strlen(str2);
    int i,j,k,m,n,flag=0;
    if(len1>len2)        //将str1和str2互换,保证str1为短字符串
    {
        strcpy(son1,str1);
        strcpy(str1,str2);
        strcpy(str2,son1);
        i=len1;len1=len2;len2=i;
    }
    i=0;
    while(len1-i)
    {
        for(j=0;j<=i;j++)        //短串的子串首字符的下标
        {
            m=0;
            for(k=j;k<j+len1-i;k++)
                son1[m++]=str1[k];
            son1[m]='\0';
            for(k=0;k<=i+len2-len1;k++)    //长串的子串首字符的下标
            {
                m=0;
                for(n=k;n<k+len1-i;n++)
                    son2[m++]=str2[n];
                son2[m]='\0';
                if(!strcmp(son1,son2))
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(flag)
            break;
        i++;
    }
    printf("%d\n",len1-i);
    return 0;
}