2 sbshso sbshso 于 2016.02.23 08:56 提问

C语言经典例题:求最大公共字符串

自己编写了很久都没写出来,求大神共享一下代码,就是给定两个字符串,求最大的公共子串,新手

3个回答

hyb1996
hyb1996   2016.02.23 10:14
已采纳

刚才那个有点错漏

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

void getMaxCommonSubstring(char*,char*);

int main(){
    char str1[1000],str2[1000];
    scanf("%s",str1);
    scanf("%s",str2);
    getMaxCommonSubstring(str1,str2);
    return 0;
}

//得到两个字符串的最大公共子串并输出 
//如果有多个最大子串只输出第一个 
void getMaxCommonSubstring(char* str1,char* str2){ 
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    //保存最大字符串及其长度 
    int maxLen = 0;
    char maxStr[1000]={0};
    //对str1和str2进行遍历 
    int i,j,k;
    for(i=0;i<len1;i++){
        for(j=0;j<len2;j++){
            //如果某个字符相同,则继续看后面最多有几个相同 
            if(str1[i]==str2[j]){
                //保存已匹配的字符串及其长度 
                int len = 1;
                char buff[1000]={0};
                buff[0]=str2[j];
                //对后面的字符遍历 
                for(k=1;i+k<len1&&j+k<len2;k++){
                    //字符不相同则跳出 
                    if(str1[i+k]!=str2[j+k])break;
                    buff[len++]=str2[j+k];
                }
                //如果匹配的字符串比原来的最大字符串更大,则拷贝到最大字符串 
                if(len>maxLen){
                    maxLen=len;
                    strcpy(maxStr,buff);
                }
            }
        }
    }
    printf("MaxCommonSubstring:\n%s\nlength:%d\n",maxStr,maxLen);
}
sbshso
sbshso 我试一下,感谢
接近 2 年之前 回复
hyb1996
hyb1996   2016.02.23 09:23

百度一下不是很多嘛
#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int longest_common_substring(char str1, char *str2)
{
int i,j,k,len1,len2,max,x,y;
len1 = strlen(str1);
len2 = strlen(str2);
int **c = new int
[len1+1];
for(i = 0; i < len1+1; i++)
c[i] = new int[len2+1];
for(i = 0; i < len1+1; i++)
c[i][0]=0; //第0列都初始化为0
for(j = 0; j < len2+1; j++)
c[0][j]=0; //第0行都初始化为0
max = -1;
for(i = 1 ; i < len1+1 ; i++)
{
for(j = 1; j < len2+1; j++)
{
if(str1[i-1]==str2[j-1]) //只需要跟左上方的c[i-1][j-1]比较就可以了
c[i][j]=c[i-1][j-1]+1;
else //不连续的时候还要跟左边的c[i][j-1]、上边的c[i-1][j]值比较,这里不需要
c[i][j]=0;
if(c[i][j]>max)
{
max=c[i][j];
x=i;
y=j;
}
}
}

//输出公共子串
char s[1000];
k=max;
i=x-1,j=y-1;
s[k--]='\0';
while(i>=0 && j>=0)
{
    if(str1[i]==str2[j])
    {
        s[k--]=str1[i];
        i--;
        j--;
    }
    else       //只要有一个不相等,就说明相等的公共字符断了,不连续了
        break;
}
printf("最长公共子串为:");
puts(s);
for(i = 0; i < len1+1; i++)         //释放动态申请的二维数组
    delete[] c[i];
delete[] c;
return max;

}
int main(void)
{
char str1[1000],str2[1000];
printf("请输入第一个字符串:");
gets(str1);
printf("请输入第二个字符串:");
gets(str2);
int len = longest_common_substring(str1, str2);
printf("最长公共连续子串的长度为:%d\n",len);
system("pause");
return 0;
}

sbshso
sbshso 恩恩,谢了,你发的上一段代码,VS2013显示未定义new int
接近 2 年之前 回复
hyb1996
hyb1996 我自己写一个给你吧,等下哈
接近 2 年之前 回复
sbshso
sbshso 百度有一些我理解不了,而且运行会出现bug
接近 2 年之前 回复
hyb1996
hyb1996   2016.02.23 10:12
 #include <stdio.h>
#include <string.h>

void getMaxCommonSubstring(char*,char*);

int main(){
    char str1[1000],str2[1000];
    scanf("%s",str1);
    scanf("%s",str2);
    getMaxCommonSubstring(str1,str2);
    return 0;
}

//得到两个字符串的最大公共子串并输出 
//如果有多个最大子串只输出第一个 
void getMaxCommonSubstring(char* str1,char* str2){ 
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    //保存最大字符串及其长度 
    int maxLen = 0;
    char maxStr[1000]={0};
    //对str1和str2进行遍历 
    int i,j,k;
    for(i=0;i<len1;i++){
        for(j=0;j<len2;j++){
            //如果某个字符相同,则继续看后面最多有几个相同 
            if(str1[i]==str2[j]){
                //保存已匹配的字符串及其长度 
                int len = 1;
                char buff[1000]={0};
                buff[0]=str2[j];
                //对后面的字符遍历 
                for(k=1;i+k<len1&&j+k<len;k++){
                    //字符不相同则跳出 
                    if(str1[i+k]!=str2[j+k])break;
                    buff[len++]=str2[j+k];
                }
                //如果匹配的字符串比原来的最大字符串更大,则拷贝到最大字符串 
                if(len>maxLen){
                    maxLen=len;
                    strcpy(maxStr,buff);
                }
            }
        }
    }
    printf("MaxCommonSubstring:\n%s\nlength:%d\n",maxStr,maxLen);
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!