首页 > 试题广场 >

公共子串计算

[编程题]公共子串计算

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

$\hspace{15pt}$ 对于给定的两个字符串 $s$ 和 $t$ ，你需要找出它们的最长公共子串的长度。

$\hspace{15pt}$ 子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
$\hspace{15pt}$ 如果字符串 $a$ 的一个子串 $a'$ 与字符串 $b$ 的一个子串 $b'$ 完全相等，那么子串 $a',b'$ 是字符串 $a,b$ 的一个公共子串。

输入描述:

$\hspace{15pt}$ 第一行输入一个长度为 $1 \leqq {\rm len}(s) \leqq 150$ 、仅由小写字母组成的字符串 $s$ 。
$\hspace{15pt}$ 第二行输入一个长度为 $1 \leqq {\rm len}(t) \leqq 150$ 、仅由小写字母组成的字符串 $t$ 。

输出描述:

$\hspace{15pt}$ 输出一个整数，代表 $s$ 和 $t$ 的最长公共子串的长度。

示例1

输入

awaabb
aawbb

输出

说明

在这个样例中， 和  都是  和  的最长公共子串。

示例2

输入

asdfas
werasdfaswer

输出

算法知识视频讲解

慧成功

#include <stdio.h>

int main() {

char a[150], b[150];

while (scanf("%149s %149s", a, b) != EOF) { // 注意 while 处理多个 case

// 64 位输出请用 printf("%lld") to

int maxlen = 0;

int dp[150][150];

for (int i = 0; i < strlen(a); i++) {

for (int j = 0; j < strlen(b); 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;

} else

dp[i][j] = 0;

if (dp[i][j] > maxlen)

maxlen = dp[i][j];

}

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

}

return 0;

}

发表于 2024-12-05 11:27:25 回复(0)

牛客774977030号

#include <stdio.h>

int max_str(char a[],char b[])

{

int la=strlen(a);

int lb=strlen(b);

int m,ma,max;

max=0;

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

{

ma=0;

for(int j=0;j<lb;j++)

{

m=0;

int p=i,q=j;

while(a[p]==b[q])

{

p--;

q--;

m++;

}

if(ma<m) ma=m;

}

if(max<ma) max=ma;

}

return max;

}

int main() {

char a[150],b[150];

gets(a);

gets(b);

int m=max_str(a,b);

printf("%d",m);

return 0;

}

发表于 2024-10-21 22:01:18 回复(0)

牛客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)

提交观点

问题信息

动态规划字符串查找

难度：

14条回答 2243收藏 50806浏览

通过挑战的用户

查看代码

牛客46027...

2023-03-04 10:16:08
36度的手指编程

2023-02-27 16:21:07
牛客80860...

2023-02-20 20:58:38
爱看剧的芹菜爱读书

2022-11-09 12:07:56
杉烟茗茗

2022-11-08 21:03:51

公共子串计算

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题