首页 > 试题广场 >

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

[编程题]查找两个字符串a,b中的最长公共子串
  • 热度指数：176224 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

数据范围：字符串长度
进阶：时间复杂度：，空间复杂度：

输入描述:
输入两个字符串


输出描述:
返回重复出现的字符
示例1

输入

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出

jklmnop
算法知识视频讲解
添加回答
C
宇g头像 宇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)
C
彭洋a头像 彭洋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)
C
牛客364244344号头像 牛客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)
C
Culaccino_5头像 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)
C
浩博_头像 浩博_ 
#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)
C
初牛小客头像 初牛小客 
#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)
C
更健康头像 更健康 
#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)
C
银风子头像 银风子 
#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)
C
牛客825450324号头像 牛客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)
C
已注销头像 已注销 
#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)
C
菜的牛头像 菜的牛
nvlrzqcjltmrejybjeshffenvkeqtbsnlocoyaokdpuxutrsmcmoearsgttgyyucgzgcnurfbubgvbwpyslaeykqhaaveqxijc
wkigrnngxehuiwxrextitnmjykimyhcbxildpnmrfgcnevjyvwzwuzrwvlomnlogbptornsybimbtnyhlmfecscmojrxekqmj

上面是较短串  不应该先输出nlo吗？？在较短串中先出现的先输出
答案输出的gcn
发表于 2022-03-27 16:53:46 回复(0)
C
HWK111头像 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)
C
花儿无缺头像 花儿无缺 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
    char str1[308], str2[308], temp[308];
    scanf("%s%s", str1, str2);
    int len1 = strlen(str1), len2 = strlen(str2), i, j, commonlen = 0, index = -1, t, flag = 0;
    if(len2 < len1){ //保证str1中存放的是较短的字符串
        strcpy(temp, str1);
        strcpy(str1, str2);
        strcpy(str2, temp);
        t = len1;
        len1 = len2;
        len2 = t;
    }
    int dp[len1][len2]; //定义dp数组：下标为i的str1和下标为j的str2最长公共子串的长度为dp[i][j]；
    memset(dp, 0, sizeof(int) * len1 * len2); //初始化dp数组；begin
    for(i = 0; i < len1; i++){
        if(str1[i] == str2[0]){
            dp[i][0] = 1;
            if(dp[i][0] > commonlen){
                commonlen = 1;
                index = i;
            }
        }
    }
    for(i = 0; i < len2; i++){
        if(str2[i] == str1[0]){
            dp[0][i] = 1;
            if(commonlen == 0){
                commonlen = 1;
                flag = 1; //只有一个公共字符为str1[0]的情况
            }
        }
    } //初始化dp数组；end
    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;
                if(dp[i][j] > commonlen){
                    commonlen = dp[i][j];
                    index = i; //记录最长公共字串在str1中的下标结束位置和长度
                }
            }
        }
    }
    if(flag == 1 && commonlen == 1){
        printf("%c", str1[0]);
    }
    else{
        if (index >= 0){
            for(i = index - commonlen + 1; i <= index; i++){
                printf("%c", str1[i]);
            }
        }
    }
    printf("\n");
    return 0;
}

发表于 2022-03-13 13:22:30 回复(0)
C
牛客991584878号头像 牛客991584878号 
#include<stdio.h>
#include<string.h>
int main()
{
    char a[300];
    char b[300];
    char a1[300];
    char b1[300];
//    while(scanf("%s\n%s\n",&a1,&b1)!=EOF)  输入指令，同样效果
    while(gets(a1)!=NULL&&gets(b1)!=NULL)
{  
    int j=0;
    int i=0;
    int num=0;
    int num1=0;  
    int k=0;
    int t=0;
    if(strlen(a1)>strlen(b1))
    {
      strcpy(a,b1);
      strcpy(b,a1);
    }
   else
   {
      strcpy(a,a1);
      strcpy(b,b1);
   }
    for(i=0;i<strlen(a);i++)
        {   
            
            for(j=0;j<strlen(b);j++)
            {    int num1=0;
                while(a[i+num1]==b[j+num1])
                {   
                    num1++;
                    
                }
             if (num1>num)
             {
                 num=num1;   
                 t=i;
             }
            }
        }
        for(k=t;k<t+num;k++)
        {
           printf("%c",a[k]);
          
            
        }
          printf("\n");
            
    }
}

发表于 2021-11-14 21:36:24 回复(0)
提交观点

问题信息

字符串
难度：
22条回答 60660浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号