列表

详情


HJ75. 公共子串计算

描述

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

注:子串的定义指一个字符串删掉其部分前缀和后缀(也可以不删)后形成的字符串。
数据范围:字符串长度:
进阶:时间复杂度:,空间复杂度:

输入描述

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

输出描述

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

示例1

输入:

asdfas
werasdfaswer

输出:

6

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 1ms, 内存消耗: 256KB, 提交时间: 2020-07-06

#include <stdio.h>
#include <string.h>
int main(void)
{
    char str1[100];
    char str2[100];

    while((scanf("%s %s",&str1,&str2))!=EOF)
    {
        int max =0;
        for(int i=0;i<strlen(str1);i++)
        {
            for(int j=0;j<strlen(str2);j++)
            {
                int m =0;
                int n =0;
                while(str1[m+i]!='\0' && str2[n+j]!='\0' && toupper(str1[m+i])==toupper(str2[n+j]))
                {
                    n++;
                    m++;
                    if(n > max)
                        max =n;
                }
            }
        }
        printf("%d\n",max);
    }
    return 0;
}

C 解法, 执行用时: 1ms, 内存消耗: 280KB, 提交时间: 2020-07-12

#include <stdio.h>
//#include <ctype.h>
#include <stdlib.h>
  
int main()
{
    char str1[100], str2[100];
    int i, j, n, m, max;
  
    while (scanf("%s %s", str1, str2) != EOF) {
        max = 0;
        for (i = 0; i < strlen(str1); i++) {
            for (j = 0; j < strlen(str2); j++) {
                n = 0;
                m = 0;
                while (str1[i + n] != '\0' && str2[j + m] != '\0'
                    && toupper(str1[i + n]) == toupper(str2[j + m])) {
                    n++;
                    m++;
                }
                if (n > max) {
                    max = n;
                }
            }
        }
        printf("%d\n", max);
    }
}

上一题