找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。

1. #include <stdio.h>
   
2. 
   
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. }

复制代码

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、解题思想永远大于代码价值～～～，自己写的代码价值大于别人的解题思想。

这是c的基础测试题，我做了好久。不过，可以直接将问题这么贴出来吗？呃，其实我想问，我可以将我的答案贴出来吗？不过还是自己编的好，自己锻炼，我做的时候，折腾了超过三小时呢。

呃，我觉得楼上Eil.tea思路很好，我就没想到。我讲讲我的思路吧。我的是，
1，找出最小字符串
2，找出最小字符串和第一或者第二个字符串的公共字符串
3，遍历子串，判断其余字符串里是否有这个，如果有，和记录最长的字串比较，长就覆盖。最终就是要就的结果了。