首页 > 试题广场 >

公共子串计算

[编程题]公共子串计算

热度指数：175996 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

数据范围：字符串长度： $1\le s\le 150\$

进阶：时间复杂度： $O(n^3)\$ ，空间复杂度： $O(n)\$

输入描述:

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

输出描述:

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

示例1

输入

asdfas
werasdfaswer

输出

算法知识视频讲解

牛客770548236号

#include <stdio.h>
#include <string.h>

int longest_substring(char *str1, char *str2) 
{
    int m = strlen(str1);
    int n = strlen(str2);

    // 创建二维数组dp
    int dp[m+1][n+1];

    // 初始化最大长度为0
    int max_len = 0;

    // 遍历两个字符串的每一个字母
    for (int i = 0; i <= m; i++) 
    {
        for (int j = 0; j <= n; j++) 
        {
            // 初始化边界条件
            if (i == 0 || j == 0) 
            {
                dp[i][j] = 0;
            }
            // 当两个字母相等时，更新dp[i][j]为前一个对角线上的数字加1
            else if (str1[i-1] == str2[j-1]) 
            {
                dp[i][j] = dp[i-1][j-1] + 1;//表示子串相等的长度
                // 更新最大长度
                if (dp[i][j] > max_len) 
                {
                    max_len = dp[i][j];
                }
            }
            else 
            {
                dp[i][j] = 0;
            }
        }
    }

    return max_len;
}

int main() 
{
    //输入
    char str1[151] = {0};
    char str2[151] = {0};
    scanf("%s",str1);
    scanf("%s",str2);
    //查找
    int len = longest_substring(str1, str2);
    //输出
    printf("%d\n", len);
    return 0;
}

编辑于 2023-12-15 14:50:14 回复(0)

向量空间

我首先想到的思路是：

（1）使用短串及其子串作为符合条件的子串，到长的串里strstr

（2）需要求最大公共子串长度，那就从假设短串长度就是最大子串长度开始，子串长度减减最为外部循环，内部循环则在该长度下轮询短串内部长度为此时长度的子串，并提出来去长串里做判断。感觉优点繁琐和易错。

注意：用来存储中间子串的临时数组长度+1。

#include <stdio.h>
#include <string.h>
/*
思路：
    使用 较短子串作为公共子串假设去长子串里使用strstr进行判断。
    对于短子串，使用两个循环，一是子串长度，二是该长度在短子串里的取值。
    题目要求最大公共子串，那子串长度就从最大开始减减

*/
int ss(int len_short, char *src, char *parent)
{
    int i,res;
    int tmp_len = len_short;
    char tmp[len_short+ 1];
    memset(tmp, 0, len_short+ 1);
    while(tmp_len) {
        for(i = 0; i <= (len_short - tmp_len); i++){    
            strncpy(tmp, &src[i], tmp_len);    
            if(strstr(parent, tmp))
            {
                return tmp_len;
            }
            memset(tmp, 0, len_short+ 1);
        }
        tmp_len--;
        memset(tmp, 0, len_short+ 1);
    }
    return tmp_len;
}

int main() {
    int len_a, len_b,len_short, i, ret;
    char a[151] = {0};
    char b[151] = {0};
    gets(a);
    gets(b);
    len_a = strlen(a);
    len_b = strlen(b);
  
    if(len_a < len_b)
    {
        len_short = len_a;
        ret = ss(len_short, a, b);
    }  
    else
    {
        len_short = len_b;
        ret = ss(len_short, b, a);  
    }
    printf("%d\n", ret);

    return 0;
}

发表于 2023-12-09 09:26:22 回复(0)

宇g

#include <stdio.h>
#include <string.h>

int main()
{
    char str1[150]={0}, str2[150]={0};
    int i, j, m, n, count;
    int max=0;

    scanf("%s %s", &str1, &str2);

    for(i=0;i<strlen(str1);i++)
    {
        for(j=0;j<strlen(str2);j++)
        {
            count=0;
            m=i;
            n=j;
            while(str1[m]==str2[n] && str1[m]!='\0')
            {
                count++;
                m++;
                n++;
            }
            max=count>max ? count : max;
        }
    }
    printf("%d",max);
    return 0;
}

发表于 2023-11-29 01:08:10 回复(0)

彭洋a

#include <stdio.h>

#include <string.h>

int main() {

char str1[151] = {'\0'};

char str2[151] = {'\0'};

while (scanf("%s %s", str1,str2) != EOF) {

int len1 = strlen(str1);

int len2 = strlen(str2);

if(len2<len1)

{

char str[151] = {'\0'};

strcpy(str, str1);

strcpy(str1, str2);

strcpy(str2, str);

int tmp = len1;

len1 = len2;

len2 = tmp;

}

int ret = 0;

for(int i = 0;i<len1;i++)

{

char tmp[151] = {'\0'};

strcpy(tmp,&str1[i]);

for(int j = 0;j<len1-i;j++)

{

tmp[len1-i-j] = '\0';

if(strstr(str2,tmp))

{

int n = len1 - j - i;

ret = n>ret?n:ret;

}

printf("%d\n",ret);

}

return 0;

}

发表于 2023-10-18 19:17:56 回复(0)

在写面经的咸鱼很机智

这个题用C语言，自测运行，和调试器结果完全不一样咋回事。

ha a的用例，自测运行结果为0。

但是我自己本机编译测试结果为1，线上调试结果也是1。。。。怪出翔。

发表于 2023-04-03 14:15:23 回复(1)

初牛小客

#include <stdio.h>
#include <string.h>

//dp[i][j]表示以字符串str1中第i个字符和str2中第j个字符为最后一个元素所构成的最长公共子串
int main() {
    char str1[150] = {};
    char str2[150] = {};
    int dp[151][151] = {0};  
    scanf("%s\n%s", str1,str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int max_len = 0;

    for(int i=1; i<=len1; i++)
    {
        for(int j=1; j<=len2; j++)
        {
            if(str1[i-1] == str2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                if(max_len < dp[i][j])
                    max_len = dp[i][j];
            }
            else 
            {
                dp[i][j] = 0;
            }
        }
    }
    printf("%d",max_len);
    return 0;
}

发表于 2023-03-05 21:59:19 回复(0)

花儿无缺

C动态规划

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
    char str1[155], str2[155];
    scanf("%s%s", str1, str2);
    int len1 = strlen(str1), len2 = strlen(str2), i, j, dp[len1][len2], commonlen = 0;
    memset(dp, 0, sizeof(int) * len1 * len2);
    for(i = 0; i < len1; i++){
        if(str1[i] == str2[0]){
            dp[i][0] = 1;
            commonlen = 1;
        }
    }
    for(i = 0; i < len2; i++){
        if(str2[i] == str1[0]){
            dp[0][i] = 1;
            commonlen = 1;
        }
    }
    for(i = 1; i < len1; i++){
        for(j = 1; j < len2; j++){
            if(str1[i] == str2[j]){
                dp[i][j] = dp[i-1][j-1] + 1;
                commonlen = commonlen > dp[i][j] ? commonlen : dp[i][j];
            }
        }
    }
    printf("%d\n", commonlen);
    return 0;
}

发表于 2022-03-13 12:34:52 回复(0)

牛客489027493号

C暴力解，简单易懂

#include <stdio.h>
#include <string.h>

#define STR_LEN 151

int GetCommonLen(char *min, char *max)
{
    int len = 0;
    for (int i = 0; i < strlen(min); i++) {
        if (min[i] == max[i]) {
            len++;
        } else {
            break;
        }
    }
    return len;
}

int main(void)
{
    char s1[STR_LEN];
    char s2[STR_LEN];
    
    while (gets(s1) && gets(s2)) {
        int len1 = strlen(s1);
        int len2 = strlen(s2);
        int min;
        int max;
        char *mins;
        char *maxs;
        if (len1 > len2) {
            min = len2;
            max = len1;
            mins = s2;
            maxs = s1;
        } else {
            min = len1;
            mins = s1;
            max = len2;
            maxs = s2;
        }
        
        int len = 0;
        for (int i = 0; i < min; i++) {
            for (int j = 0; j < max; j++) {
                // 从相同的地方向后寻找
                if (mins[i] == maxs[j]) {
                    int tmp = GetCommonLen(mins + i, maxs + j);
                    len = len > tmp ? len : tmp;
                }
            }
        }
        printf("%d\n", len);
    }
}

发表于 2021-11-02 23:13:52 回复(0)

李拓爱编码

#include <stdio.h>
#include <string.h>

#define MAX_STR 1000

char* longest_common_substring(const char *str1,const char *str2);

char* longest_common_substring(const char *str1,const char *str2)
{
    int str1len = strlen(str1);
    int str2len = strlen(str2);
    int i,j,index,max=0,num=0;
    int start;

    //将两个字符串看做两个直尺，固定一个直尺，另外一个从头到尾开始移动，逐一与固定的直尺比较值。
    for(i = 0; i < str1len; i++)
    {
        for(j = 0; j < str2len; j++)
        {
            //这里的start1、start2是比较关键的
            int start1=i;
            int start2=j;
            while((start1 <= str1len-1) && (start2 <= str2len-1) && (str1[start1++] == str2[start2++]))
                num++;
            if(num > max)//如果num是当前最大匹配的个数，则赋给max，并且在start记下str1最长匹配开始的位置
            {
                max=num;
                start=i;
            }
            num=0;//如果num不是当前最大的，则赋为0值继续循环
        }
    }
    char *str=(char *)malloc(max + 1);
    strncpy(str,str1 + start,max); //从字符串str1的start位置开始，拷贝max个字符到str中，这就是我们找出的最大子串
    str[max] = '\0';
    return str;
}

int main()
{
char str1[MAX_STR];
char str2[MAX_STR];

while (scanf("%s %s", str1, str2) != EOF)
{
char* str3 = NULL;
str3 = longest_common_substring(str1, str2);

printf("%d\n", strlen(str3));

free(str3);
str3 = NULL;
}

return 0;
}

发表于 2021-10-08 16:27:16 回复(0)

海饼干666

#include <stdio.h>

int main()
{
    int len1 = 0, len2 = 0;
    int line = 0;
    char array1[1024], array2[1024];
    char buff;
    
    while(scanf("%c",&buff) != EOF)
    {
        if(buff == '\n') line++;
        else
        {
            if(0 == line)
            {
                array1[len1++] = buff;
            }
            else if(1 == line)
            {
                array2[len2++] = buff;
            }
        }
        if(2 == line)
        {
            int maxlen = 0;
            int map[len1][len2];
            for(int i = 0; i < len1; i++)
            {
                for(int j = 0; j < len2; j++)
                {
                    if(array1[i] == array2[j])
                    {
                        if(i==0 || j==0) map[i][j] = 1;
                        else map[i][j] = map[i-1][j-1]+1;
                        maxlen = maxlen < map[i][j] ? map[i][j]:maxlen;
                    }
                    else map[i][j] = 0;
                }
            }
            printf("%d\n",maxlen);
            line = 0;
            len1 = 0;
            len2 = 0;
        }
        
    }
    return 0;
    
}

发表于 2021-09-05 18:46:40 回复(0)

80后大叔

参考大佬们的动态规划写的
#include<stdio.h>
int getSub(char* a, char* b){
    int maxLen=0;
    int n=strlen(a);
    int m=strlen(b);
    int dp[1024][1024];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i]==b[j]){
                if(i==0||j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                maxLen=maxLen>dp[i][j]?maxLen:dp[i][j];
            }else{
                dp[i][j]=0;
            }
        }

    }
    return maxLen;
}
int main(){
    char a[1024];
    char b[1024];
    int num=0;
    fgets(a,1024,stdin);
    fgets(b,1024,stdin);
    num=getSub(a,b);
    printf("%d\n",num);
}

发表于 2021-08-03 19:56:09 回复(0)