华为机试题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;
}