首页 > 试题广场 >

查找两个字符串a,b中的最长公共子串

[编程题]查找两个字符串a,b中的最长公共子串

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

$\hspace{15pt}$ 对于给定的两个字符串 $s$ 和 $t$ ，你需要找出它们的最长公共子串。特别地，如果存在多个答案，输出在较短串中最先出现的那个。

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

输入描述:

第一行输入一个长度为 、仅由小写字母组成的字符串 。
第二行输入一个长度为 、仅由小写字母组成的字符串 。

输出描述:

输出一个字符串，代表  和  的最长公共子串。如果存在多个答案，输出在较短串中最先出现的那个。

示例1

输入

awaabb
aawbb

输出

aa

说明

在这个样例中， 和  都是  和  的最长公共子串，但  在较短串  中首先出现，因此输出 。

示例2

输入

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出

jklmnop

算法知识视频讲解

久辰天

学会用strstr（）函数

思路为先确认长短，在从短的全段开始从长到短开始匹配

#include <stdio.h>

#include <string.h>

int main() {

char s[310], t[310], jq[310]; //字符串数组--jq[310]

char duan[310], chang[310];

int c_s, c_t, duan1, chang1; //字符串长度

int count = 0; //公共子串长度计数

int max = 0; //最长子串长度计数

scanf("%s\n%s", s, t);

c_s = strlen(s); //输入的s长度

c_t = strlen(t); //输入的t长度

if (c_t > c_s) { //确定长短

duan1 = c_s;

strcpy(duan, s);

chang1 = c_t;

strcpy(chang, t);

} else {

duan1 = c_t;

strcpy(duan, t);

chang1 = c_s;

strcpy(chang, s);

}

for (int i = 0; i < duan1; i++) { //开始循环短的开始

for (int j = duan1; j > i; j--) { //从字符串（duan[i]~duan[duan1-1]）

char sub_str[310];

int len = j - i; //字符长度为j-i (末尾序号-首位序号+1)

strncpy(sub_str, duan + i, len); //将字符串通过strncpy复制到过渡字符串sub_str

sub_str[len] = '\0'; //为sub_str输入终止符长度为len，

//因为角标从0开始，所以角标len对应终止

// 检查子串是否在长字符串中

if (strstr(chang, sub_str) != NULL) { //检查sub_sr是否为chang的子串，如果是则返回角标位置，不是在则返回null

if (len > max) { //不为null,则是子串，判断子串长度

max = len;

strcpy(jq, sub_str); //新子串更长，将其复制进入字符串jq

}

printf("%s", jq);

return 0;

}

发表于 2026-01-01 23:25:32 回复(0)

牛油果114514

给各位老师表演一个暴力解题，下午刚努力理解了编辑距离，动态规划实在整不明白

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

#define maxstrlen 300
// 暴力方法测试通过，时间长达24ms
int main()
{
    char s[maxstrlen] = {0};
    char t[maxstrlen] = {0};
    char temp[maxstrlen] = {0};
    int sh, ln, mslen = 0;
    int i, j, k, l;

    scanf("%s %s", s, t);
    if (strlen(s) > strlen(t))
    {
        strcpy(temp, s);
        strcpy(s, t);
        strcpy(t, temp);
    }
    sh = strlen(s);
    ln = strlen(t);
    for (i = sh; i >= 2; i--) // 外循环，子串的长度
    {
        for (l = 0; l <= sh - i; l++) // 中循环从开头遍历短字符串,先遍历谁就是以谁的子串优先
        {
            for (j = 0; j <= ln - i; j++) // 内循环从开头遍历长字符串
            {
                if (strncmp(&s[l], &t[j], i) == 0) // 判断，同步了外循环的子串长度，先从最长的开始，找到就结束
                {
                    for (k = 0; k < i; k++) // 子串，长度和外循环一致，头部在内循环中，从长的字符串中复制
                    {
                        printf("%c", t[j + k]);
                    }
                    return 0;
                }
            }
        }
    }
    return 0;
}

发表于 2025-01-18 20:59:30 回复(0)

春种一粒粟

#include <stdio.h>

#include <string.h>

int main() {

char str1[301];

char str2[301];

char *phead,*plong,tempchar;

int i,j,shortlen;

scanf("%s",str1);

scanf("%s",str2);

phead=str1;

plong=str2;

if(strlen(str1)>strlen(str2))

{

phead=str2;

plong=str1;

}

shortlen=strlen(phead);

for(i=shortlen;i>=1;i--)

{

for(j=0;j<shortlen-i+1;j++)

{

tempchar= phead[j+i];

phead[j+i]='\0';

if(strstr(plong,(phead+j)))

goto result;

phead[j+i]=tempchar;

}

if(i==0)

{

printf("");

}

result:

printf("%s",(phead+j));

return 0;

}

发表于 2025-01-05 13:11:25 回复(0)

宇g

#include <stdio.h>

#include <string.h>

int main()

{

char a[300]={0}, b[300]={0}, str[300]={0};

char temp[300]={0};

int i, j, k, o, m, n;

int max=0;

scanf("%s %s", &a, &b);

if(strlen(b)<strlen(a)) //如果字符串b比a短则交换两个字符串

{

strcpy(temp,a);

strcpy(a,b);

strcpy(b,temp);

}

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

{

for(j=0;j<strlen(b);j++)

{

m=i, n=j;

o=j;

int count=0;

while(a[m]==b[n])

{

count++;

m++;

n++;

}

if(count>max) //判断，如果更长则替换

{

max=count;

for(k=0;k<count;k++,o++)

{

str[k]=b[o];

}

printf("%s", str);

return 0;

}

发表于 2023-11-24 16:44:03 回复(0)

彭洋a

#include <stdio.h>

#include <string.h>

int main() {

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

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

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

int len1 = strlen(str1);

int len2 = strlen(str2);

int ret = 0;

char* ptr = str1;

if(len1>len2)//确保较短的字符串在str1,len1表示较短字符串的长度

{

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

strcpy(tmp,str1);

strcpy(str1,str2);

strcpy(str2,tmp);

str1[len2] = '\0';

int a = len1;

len1 = len2;

len2 = a;

}

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

{

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

strcpy(tmp,&str1[i]);

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

{

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

if(strstr(str2,tmp))

{

int num = len1 - j - i;

if(num>ret)

{

ret = num;

ptr = &str1[i];

}

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

{

printf("%c",ptr[i]);

}

return 0;

}

发表于 2023-10-18 15:50:30 回复(0)

牛客364244344号

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

#define N 301

int main()
{
    char a[N] = {0};
    char b[N] = {0};
    char c[N] = {0};
    char *shortStr, *longStr;
    scanf("%s %s", a, b);
    int lenA = strlen(a);
    int lenB = strlen(b);
    int cnt = 0, k = 0, cntTem = 0;
    int shortLen, longLen;;
    if(lenA > lenB){
        longStr = a;
        shortStr = b;
        longLen = lenA;
        shortLen = lenB;
    }else{
        longStr = b;
        shortStr = a;
        longLen = lenB;
        shortLen = lenA;
    }
    for (int i = 0; i < shortLen; i++){
        for(int j = 0; j < longLen; j++){
            cntTem = 0, k = 1;
            if(*(shortStr+i) == *(longStr+j)){
                cntTem++;
                while(*(shortStr+i+k) == *(longStr+j+k)){
                    k++;
                    cntTem++;
                }
                if(cntTem > cnt){
                    for(int l = 0; l < cntTem; l++){
                        c[l] = *(shortStr+i+l);
                    }
                    c[cntTem] = 0;
                    cnt = cntTem;
                }
            }
        }
    }
    printf("%s\n", c);
    return 0;
}

发表于 2023-10-12 21:44:45 回复(0)

Culaccino_5

#include <stdio.h>
#include <string.h>
int main() {
    char stra[300], strb[300], out[300], buf[300] = { 0 };
    int i, j,cnt = 0, max = 0;
    scanf("%s", stra);
    scanf("%s", strb);
    if (strlen(stra) > strlen(strb)) {
        strcpy(buf, strb);
        strcpy(strb, stra);
        strcpy(stra, buf);
    }//保证短串一定是stra
    for (i = 0; i < strlen(stra); i++) {
        for (j = 0; j < strlen(strb); j++) {
            i = i - cnt;
            cnt = 0;
            memset(buf, 0, 300);
            while (stra[i] == strb[j]) {
                buf[cnt] = stra[i];
                i++;
                cnt++;
                j++;
            }
            if (cnt > max) {
                max = cnt;
                strcpy(out, buf);
                j--;
            }
        }
    }
    printf("%s", out);
    return 0;
}

发表于 2023-09-14 15:05:33 回复(0)

浩博_

#include <stdio.h>

int main()
{
	int len1,len2,loc = 0,len_sub = 0,i,j,k = 0;
	char arr1[300] = { 0 }, arr2[300] = { 0 };
	char same_str[300] = { 0 };

	gets(arr1); 
	gets(arr2);
	len1 = strlen(arr1);
	len2 = strlen(arr2);

	if (len1 < len2) {
		for (i = 0; i < len1; i++) {
			for (j = 0; j < len2; j++) {
				if (arr2[j] == arr1[i]) {
					for (k = 0;; k++) {
						if (arr2[j + k] != arr1[i + k])
							break;
					}
					if (k > len_sub) {
						len_sub = k;
						strncpy(same_str,arr1 + i,len_sub);
					}
				}
			}
		}
	}
	else if (len2 < len1) {
		for (i = 0; i < len2; i++) {
			for (j = 0; j < len1; j++) {
				if (arr1[j] == arr2[i]) {
					for (k = 0;; k++) {
						if (arr1[j + k] != arr2[i + k])
							break;
					}
					if (k > len_sub) {
						len_sub = k;
						strncpy(same_str, arr2 + i, len_sub);
					}
				}
			}
		}
	}

	for(i = 0;i < len_sub;i++)
		printf("%c",same_str[i]);

}

发表于 2023-09-10 16:37:36 回复(0)

初牛小客

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

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

    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int min_len = len1>len2 ? len2:len1; 
    int max_len = len1<len2 ? len2:len1; 
    char* min_str = len1>len2 ? str2:str1;
    char* max_str = len1<len2 ? str2:str1;
    int sub_index = 0;
    int sub_max = 0;
    for(int i=1; i<=min_len; i++){          //从较短串中先遍历
        for(int j=1; j<=max_len; j++){
            if(min_str[i-1] == max_str[j-1])      //相等就能构成更长的公共子串
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else
            {
                dp[i][j] = 0;
            }
            if(dp[i][j] > sub_max)
            {
                sub_max = dp[i][j];     //记录最长公共子串长度和最后一个字符的位置
                sub_index = i;
            }
        }
    }

    //输出在较短串中最先出现的那个
    min_str[sub_index] = '\0';
    printf("%s", min_str+sub_index-sub_max);

    return 0;
}

发表于 2023-03-03 21:13:07 回复(0)

更健康

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

int dp[300][300];
int maxLen;
void getIndex(char *shortStr, char *longStr)
{
    int index;
    for (int i=0; i< strlen(shortStr); i++) {
        for (int j=0; j<strlen(longStr); j++) {
            if (shortStr[i] == longStr[j]) {
                if (i ==0 || j == 0)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i-1][j-1] + 1;
            }
            if (maxLen < dp[i][j]) {
                maxLen = dp[i][j];
               index = i;
            }
        }
    }
     for (int i=index-maxLen+1; i < index + 1; i++)
            printf("%c", shortStr[i]);
}

int main(void)
{
    char str1[300] = {0};
    char str2[300] = {0};
    
    scanf("%s", str1);
    getc(stdin);
    scanf("%s", str2);
    int maxLen = 0;
    int index = 0;

    
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    
    if (len1 < len2)
        getIndex(str1, str2);
    else if(len1 >len2)
        getIndex(str2,str1);
        
    printf("\n");
}

发表于 2022-08-23 22:11:02 回复(0)

银风子

#include <stdio.h>
#include <string.h>
int main(void){
    char str1[300]={0};
    char str2[300]={0};
    int dp[301]={0};
    int temp[301]={0};
    char out[300]={0};
    char *str_long;
    char *str_short;
    int max_length=0,max_port=0,length1,length2;
    fgets(str1,sizeof(str1),stdin);
    fgets(str2,sizeof(str2),stdin);
   // printf("%s%s",str1,str2);  
    length1=strlen(str1)-1;
    length2=strlen(str2)-1;
   // printf("%d,%d",length1,length2);  
    if(length1>length2){
        str_long=str1;
        str_short=str2;
    }else{
        str_long=str2;
        str_short=str1;
    }
   //printf("%s%s",str_long,str_short); 
    for (int i=0;i<strlen(str_short)-1;i++){
        for(int j=0;j<strlen(str_long)-1;j++){
            if(str_short[i]==str_long[j]){
                dp[j+1]=temp[j]+1;//j+1对应str2 j的位置
               // printf("%c,%d\n",str1[i],dp[j+1]);
            }else{
                dp[j+1]=0;
            }
            if(dp[j+1]>max_length){
                max_length=dp[j+1];
                max_port=j;
            }
        }
        memcpy(temp, dp, sizeof(int)*301);
    }
    strncpy(out, str_long + 1 +max_port -max_length, max_length);
    printf("%s",out);
    //printf("\n%d,%d",max_length,max_port);
    return 0;
}

主要是输出要按照短的先输出，循环中需要顺序

发表于 2022-08-04 17:58:58 回复(0)

牛客825450324号

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

int main(){
char a[300];
char b[300];
char com[300] = {0};
char tmp[300] = {0};
int lena = 0;
int lenb = 0;
int max = 0;
int l = 0;
int r = 0;
int cmpn = 0;

gets(a);
gets(b);
lena = strlen(a);
lenb = strlen(b);

if(lena>lenb){
strcpy(tmp, a);
strcpy(a,b);
strcpy(b, tmp);
}
lena = strlen(a);
lenb = strlen(b);

l = 0;
r = lena -1;
while(l<lena){

while(l<=r){
cmpn = r-l+1;
memset(tmp, 0, sizeof(tmp));
strncpy(tmp, a+l, cmpn);
if(strstr(b, tmp)==NULL){
r--;
continue;
}else{
if(max<cmpn){
max = cmpn;
strcpy(com, tmp);
}
break;
}
}
l++;
r = lena -1;
}
printf("%s", com);
}

发表于 2022-05-06 10:30:35 回复(0)

已注销

#include <stdio.h>
#include <string.h>
#define    N    300
int main()
{
    char str1[N],str2[N],son1[N],son2[N];
    scanf("%s%s",str1,str2);
    int len1=strlen(str1),len2=strlen(str2),i=0,j,k,t,u,flag=0;
    if(len1>len2)
    {
        strcpy(son1,str1);
        strcpy(str1,str2);
        strcpy(str2,son1);
        j=len1;len1=len2;len2=j;
    }
    while(len1-i>0)
    {
        for(j=0;j<=i;j++)    //短串中子串开始的位置
        {
            t=0;
            for(k=j;k<j+len1-i;k++)
            {
                son1[t++]=str1[k];
            }
            son1[t]='\0';
            for(k=0;k<=i+len2-len1;k++)    //长串中子串开始的位置
            {
                t=0;
                for(u=k;u<k+len1-i;u++)
                {
                    son2[t++]=str2[u];
                }
                son2[t]='\0';
                if(!strcmp(son1,son2))
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(flag)
            break;
        i++;
    }
    printf("%s\n",son1);
    return 0;
}

暴力求解了，感觉挺笨的

发表于 2022-05-02 18:16:03 回复(0)

菜的牛

nvlrzqcjltmrejybjeshffenvkeqtbsnlocoyaokdpuxutrsmcmoearsgttgyyucgzgcnurfbubgvbwpyslaeykqhaaveqxijc

wkigrnngxehuiwxrextitnmjykimyhcbxildpnmrfgcnevjyvwzwuzrwvlomnlogbptornsybimbtnyhlmfecscmojrxekqmj

上面是较短串不应该先输出nlo吗？？在较短串中先出现的先输出

答案输出的gcn

发表于 2022-03-27 16:53:46 回复(0)

HWK111

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void find(char c1[],int a,char c2[],int b)//a<=b
{
    int i,j,add=0,max=0,x;
    for(i=0;i<a;i++)
    {
        for(j=0;j<b;j++)
        {
            while(c1[i+add]==c2[j+add])
            {
                add++;
            }
            if(add>max)
            {
                max=add;
                x=i;
            }
            add=0;
        }
    }
    for(i=x,j=0;j<max;i++,j++)
    {
        printf("%c",c1[i]);
    }
}
int main()
{
    char arr1[301]={0};
    char arr2[301]={0};
    scanf("%s\n%s",arr1,arr2);
    int len1=strlen(arr1);
    int len2=strlen(arr2);
    if(len1>=len2)
        find(arr2,len2,arr1,len1);
    else
        find(arr1,len1,arr2,len2);
    return 0;
}

发表于 2022-03-20 16:49:29 回复(0)

提交观点

问题信息

字符串

难度：

25条回答 2552收藏 65830浏览

通过挑战的用户

查看代码

AHAHAHAHA6

2023-03-06 11:17:33
奈何笑不了

2023-03-02 16:44:55
牛客15248...

2023-01-25 02:03:36
思钱想厚008

2023-01-08 00:27:36
梧桐上的小鸟

2022-12-18 16:00:23

查找两个字符串a,b中的最长公共子串

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题