A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

找出多个字符串中的最大公共子字符串,如“nbitheimanb”和“itheia”的最大子串是:”ithei”。
  1. #include <stdio.h>

  2. int main() {
  3.     char a[] = {'n','b','i','t','h','e','i','m','q','n','b'};
  4.     char b[] = {'i','t','h','e','i','q'};
  5.     int A =sizeof(a);
  6.     int B =sizeof(b);
  7.     int l =0;//当前最大长度
  8.     int L =0;//最大长度
  9.     int I = 0;//最大长度的起始位置
  10.     for (int i =0; i < A;  i++) {
  11.         for (int j = 0; j < B; j++) {
  12.             for (int k = 0 ; k + j < B; k++) {
  13.                 if (a[k + i] == b[j + k]) {
  14.                     l++;
  15.                 }else{
  16.                         if (L < l){
  17.                             L = l;
  18.                             I = i;
  19.                         }
  20.                     l = 0;
  21.                     break;
  22.                 }
  23.             }
  24.         }
  25.     }
  26.     for (int i =0 ; i < L; i++) {
  27.         printf("%c",a[I + i]);
  28.     }
  29.     return0;
  30. }
复制代码

10 个回复

倒序浏览
I=i这句没必要吧,反而是加上了有点问题;
还有这个计算两个串,不是多个串
回复 使用道具 举报
wowthe1st 发表于 2015-8-16 11:39
I=i这句没必要吧,反而是加上了有点问题;
还有这个计算两个串,不是多个串 ...

跪求给出这个题的解法
回复 使用道具 举报
#include "stdlib.h"
#include <stdio.h>

int main()
{

        char * findMaxCommonStr(char [][100],int);
        int i;
        char strs[3][100];//设置为输入三个字符串
        char *p;
        printf("输入三个字符串\n");
        for(i=0;i<3;i++)
                scanf("%s",strs[i]);
        p=findMaxCommonStr(strs,3);
       
        printf("最大子串是:%s\n",p);
        free(p);       
        return 0;
}

char * findMaxCommonStr(char strs[][100],int len)
{
        int findSubStrInStr(char *,char *);
        int appendChar(char **,char);
        void deleteLastChar(char*);
        int countStrLen(char *);
       
        char *commonStr=(char*) malloc(1),*commonStr2;//声明两个字符串,commonStr用来存储查找到的最大子串,commonStr2用来存储当前查找的子串
        *commonStr=0;//默认无共同子串
       
        int i,flag;
        char *p,*p2;
        for(p=strs[0];*p!=0;p++)//循环第一个字符串
        {
                commonStr2=(char*)malloc(1);*commonStr2=0;//当前查找的子串初始化为长度为0的字符串
                flag=1;//标识符,用来标识是否当前子串在三个目标字符串中都查找到
                for(p2=p;flag&&*p2!=0;p2++)//从循环的第一个字符串的当前字符开始寻找,若已经到字符串结束或者出现未找到情况,跳出循环
                {
                        appendChar(&commonStr2,*p2);//将当前查找的子串追加一个紧接其后的字符
                        for(i=1;i<len&&flag;i++)//循环处第一个字符串后的所有字符串,进行对子串的查找
                        {
                                flag=(findSubStrInStr(strs[i],commonStr2)!=-1);//若该子串在字符串中存在,则flag继续为1,不存在则flag变为0
                       
                        }
                }
                if(!flag) deleteLastChar(commonStr2);//当flag为0的情况,则说明当前子串在其他字符串中未找到,需要删除最后一位才是当前循环的共同子串
               
                if(countStrLen(commonStr)<countStrLen(commonStr2))//若新的子串长度大于旧的子串,则将旧的子串赋值为新的长度更长的子串
                        free(commonStr),commonStr=commonStr2;  //释放commonStr空间,将新的最大子串commonStr2赋值给commonStr
                else free(commonStr2);// 否则释放commonStr2空间,其他不变
        }
        return commonStr;

}

int findSubStrInStr(char *str,char *substr)//从一个字符串中查找一个子串,返回第一次找到该子串的位置
{
        int index=-1;//没找到则返回-1
        char *sp,*p,*p2;
        for(sp=str;*sp!=0;sp++)
        {
               
                for(p=substr,p2=sp;*p!=0&&*p2!=0&&*p==*p2;p++,p2++);
                if(*p==0)
                {
                        index=sp-str;break;//若*p的值为0,说明子串从头到尾都能在目标串中找到,将找到的下标赋值给index,并跳出循环
                }
        }
        return index;
       
}

void deleteLastChar(char *str)//删除字符串最后一个字符
{
        int countStrLen(char *);
        *(str+countStrLen(str)-1)=0;//将字符串最后一个字符设置为0达到删除目的
}

int appendChar(char **src,char c)  //往字符串后面添加字符
{        //使用指向指针变量的指针变量,可以改变调用该函数的函数中该指针变量的值
        int countStrLen(char *);
        int newlen=countStrLen(*src)+2;//该字符串在内存中所占空间长度加1(需要将字符串长度+2,因为字符串长度不包括最后的0)
        *src=(char*)realloc(*src,newlen);//将该字符串在内存中空间长度增加1,并将增加后新字符串的首地址赋值给原先的字符指针

        *(*src+newlen-1)=0;//将0移至最后一位
        *(*src+newlen-2)=c;//原先0的位置赋值为需要添加的字符c
        return newlen;
}

int countStrLen(char * p)  //计算字符串长度
{
        int count;
        for(count=0;*p;p++,count++);
        return count;
}
回复 使用道具 举报
当然要是单是这道题的话,大可不必这么麻烦,不过思想跟上面是一样的;
我写了一些比较通用的函数来做,只针对这道题的话,这些函数没什么必要写
回复 使用道具 举报
最大公共子串,这个用lsc算法更好吧
回复 使用道具 举报
看起来好复杂
回复 使用道具 举报
看着头都有点晕了,好流弊的样子
回复 使用道具 举报
这道题目哪那么麻烦,解题思路
1、找出最短的字符串(因为最长公共字串不可能比最短的字符串还长,并且公共字串一定是该字符串的字串)。
2、从该字符串的最大字串依次枚举,假设字符串是"abcd",枚举方式是"abcd"  "abc"  "bcd" "ab" "bc" "cd" "a" "b" "c" "d",取 int len=strlen(str),for i = len --->1, for j=0-len-i-1,
3、将取出的每个字串和其他字符串去判定,如果都存在这个字串,直接就有结果了,退出循环优化效率。因为是从最长的开始枚举的,所以一旦有结果,就是最后的结果(当然最大字串可能有多个,这个题目没要求,暂不考虑)
4、解题思想永远大于代码价值~~~,自己写的代码价值大于别人的解题思想。
回复 使用道具 举报
CQY 中级黑马 2015-8-24 10:52:11
10#
这是c的基础测试题,我做了好久。不过,可以直接将问题这么贴出来吗?呃,其实我想问,我可以将我的答案贴出来吗?不过还是自己编的好,自己锻炼,我做的时候,折腾了超过三小时呢。
回复 使用道具 举报
CQY 中级黑马 2015-8-24 10:58:55
11#
呃,我觉得楼上Eil.tea思路很好,我就没想到。我讲讲我的思路吧。我的是,
1,找出最小字符串
2,找出最小字符串和第一或者第二个字符串的公共字符串
3,遍历子串,判断其余字符串里是否有这个,如果有,和记录最长的字串比较,长就覆盖。最终就是要就的结果了。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马