黑马程序员技术交流社区

标题: 习题：求出两个字符串的最长公共子串 的扩展练习 [打印本页]

---

作者: 李天昊    时间: 2015-12-4 07:16
标题: 习题：求出两个字符串的最长公共子串 的扩展练习

原题：求出两个字符串的最长公共子串  

对原题进行了一些小扩展，能够实现由用户自由输入需要比较的字符串个数，并依次自由输入每个字符串，最后输出几个字符串的最长公共子串。

没有用到string的任何函数，求大神指教不足之处

#include <stdio.h>

//函数作用： 比较ch1 和ch2两字符指针所指的字符串中的最大子串，并将其存入ch3中

void String_getpublicstring(char *ch1,char *ch2,char *ch3)

{

    //index用于记录最长子串的开始角标，maxCount记录最大字符串长度，count记录每个公共子串的长度用于和maxCount比较，以确定是否刷新maxCount和index的数值

    int   index = 0,maxCount = 0,count = 0;

    //遍历ch1所指的字符串

    for (int i = 0; *(ch1+i)!='\0'; i++)

    {

        //遍历ch2所指字符串，与每一个ch1字符串的字符元素相比较

      for (int j = 0;*(ch2+j)!='\0'; j++)

      {

          //如果找到了第一个相同的字符，就进入分支，进行下一步的比较

          if (*(ch1+i)==*(ch2+j)) {

              //每次比较前count要置零

            count = 0;

        for (int k = 0;*(ch1+i+k)==*(ch2+j+k)&&*(ch1+i+k)!='\0'&&*(ch2+j+k)!='\0';k++) {

            count++;

        }

              //将当前比较得到的子串长度与历史最大子串长度比较，以确定是否更新最大长度，和最长子串的index

              if (maxCount<count)

                {

                    maxCount = count;

                    index = i;

                }

          }

        }

    }

    int j = 0;

    //依据比较所得的最大长度和串首索引将子串存入ch3所指的字符串

    for (int k = index; k<index+maxCount; k++) {

        *(ch3+(j++)) = *(ch1+k);

    }

    //最后再结果字符串的末尾加'\0'

    *(ch3+j) = '\0';

}

//函数作用 输出提示信息，并将用户输入的字符串录入对应字符串数组中

void PrintAndScanf(char *s)

{

    int i = 0;

    char ch = 0;

    //用static 延长num变量生命周期，这样可以记录输入字符串的次数并输出

    static int num = 1;

    printf("请输入第%d个字符串，以回车键结束：\n",num++);

    //典型的以回车符判定结束的字符串录入代码块

    scanf("%c",&ch);

    while (ch!='\n') {

        *(s+i++)= ch;

        scanf("%c",&ch);

    }

    //为了程序安全性，习惯将每次录入完的字符串末尾手动加'\0'

    *(s+i) = '\0';

}

int main(int argc, const char * argv[]) {

    int num = 0;

    printf("请输入参加比较的字符串个数：");

    scanf("%d",&num);

    //此处要用一个getchar吸收回车键，不然下面的第一次PrintAndScanf函数会录入缓存区剩余的回车

    getchar();

    //创建一个足够大的二维数组存储用户输入的每一组字符串。

    //此处本想为了节省内存，写一个根据上面num数值，创建响应行数的二维数组，但是绞尽脑汁也没有想出来，有哪位大神会写的，求指教。

    char ch[20][100]={0};

    //做num次录入操作，将用户输入的字符串存到二维数组ch中

    for (int i = 0; i<num; i++) {

        PrintAndScanf(*(ch+i));

    }

    //比较二维数组中 前两个字符串，将比较结果存入第一个字符串，因为比较函数中最后有加'\0'的操作，而比较后第一组字符串中的内容就没有用处了，可以覆盖；所以可以一直用第一组字符串接收比较结果

    String_getpublicstring(*ch,*(ch+1), *ch);

    for (int i = 2; *(ch+i)[0]!='\0'; i++) {

        String_getpublicstring(*(ch+i), *ch, *ch);

    }

    //字符串比较函数操作完，结果就存入了二维数组ch中的第一行字符串中，下面提取其长度信息

   for (int i = 0; i<100; i++) {

        if (*(*ch+i)=='\0') {

            printf("最大子字符串长度：%d,字符串为：",i);

            break;

        }

    }

   //因为String_getpublicstring中最后有为结果字符串加'\0'的操作，因此下面可以直接输出结果

    printf("%s\n",*ch);

    return 0;

}

---

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

黑马程序员IT技术论坛 X3.2