黑马程序员技术交流社区

标题: 找出多个字符串中的最大公共子字符串（c） [打印本页]
作者: 胥鹏飞    时间: 2015-8-16 11:33
标题: 找出多个字符串中的最大公共子字符串（c）
找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。
  1. #include <stdio.h>

  3. int main() {
  4.     char a[] = {'n','b','i','t','h','e','i','m','q','n','b'};
  5.     char b[] = {'i','t','h','e','i','q'};
  6.     int A =sizeof(a);
  7.     int B =sizeof(b);
  8.     int l =0;//当前最大长度
  9.     int L =0;//最大长度
  10.     int I = 0;//最大长度的起始位置
  11.     for (int i =0; i < A;  i++) {
  12.         for (int j = 0; j < B; j++) {
  13.             for (int k = 0 ; k + j < B; k++) {
  14.                 if (a[k + i] == b[j + k]) {
  15.                     l++;
  16.                 }else{
  17.                         if (L < l){
  18.                             L = l;
  19.                             I = i;
  20.                         }
  21.                     l = 0;
  22.                     break;
  23.                 }
  24.             }
  25.         }
  26.     }
  27.     for (int i =0 ; i < L; i++) {
  28.         printf("%c",a[I + i]);
  29.     }
  30.     return0;
  31. }
复制代码
作者: wowthe1st    时间: 2015-8-16 11:39
I=i这句没必要吧，反而是加上了有点问题；
还有这个计算两个串，不是多个串
作者: 胥鹏飞    时间: 2015-8-16 13:23
wowthe1st 发表于 2015-8-16 11:39
I=i这句没必要吧，反而是加上了有点问题；
还有这个计算两个串，不是多个串 ...

跪求给出这个题的解法
作者: wowthe1st    时间: 2015-8-16 16:53
#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;
}
作者: wowthe1st    时间: 2015-8-16 16:54
当然要是单是这道题的话，大可不必这么麻烦，不过思想跟上面是一样的；
我写了一些比较通用的函数来做，只针对这道题的话，这些函数没什么必要写
作者: 永远的EOF    时间: 2015-8-17 00:52
最大公共子串，这个用lsc算法更好吧
作者: dzb5461883    时间: 2015-8-17 07:14
看起来好复杂
作者: 同舟ing    时间: 2015-8-24 09:48
看着头都有点晕了，好流弊的样子
作者: Eil.tea    时间: 2015-8-24 10:20
这道题目哪那么麻烦，解题思路
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
这是c的基础测试题，我做了好久。不过，可以直接将问题这么贴出来吗？呃，其实我想问，我可以将我的答案贴出来吗？不过还是自己编的好，自己锻炼，我做的时候，折腾了超过三小时呢。
作者: CQY    时间: 2015-8-24 10:58
呃，我觉得楼上Eil.tea思路很好，我就没想到。我讲讲我的思路吧。我的是，
1，找出最小字符串
2，找出最小字符串和第一或者第二个字符串的公共字符串
3，遍历子串，判断其余字符串里是否有这个，如果有，和记录最长的字串比较，长就覆盖。最终就是要就的结果了。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2