黑马程序员技术交流社区

标题: 找多个字符串共同字符串 [打印本页]
作者: 222222222222    时间: 2016-6-2 22:02
标题: 找多个字符串共同字符串
找出多个字符串中的最大公共子字符串，如“nbitheimanb”和“itheia”的最大子串是：”ithei”。（C语言）
#include <stdio.h>
#include <string.h>
int main()
{
    //1.定义字符串数组
    char s1[100], s2[100];
    //2.定义一个二维数组存放指定变量（两个字母相等，值为1，不相等，值为0）
    int a[100][100];
    //3.定义变量记录公共字符串长度
    int MaxLenth = 0;
    //4.定义变量记录相等字符的最后的地址
    int adds = 0;
    //5.提示用户输入第一个字符串
    printf("请输入第一个字符串：\n");
    //6.接收用户输入的第一个字符串数组
    scanf("%s", s1);
    //7.提示用户输入第二个字符串
    printf("请输入第二个字符串\n");
    //8.接收用户输入的第二个字符串数组
    scanf("%s", s2);
    //9.遍历字符串s1
    for(int i = 0; i < strlen(s1); i++)
    {
        //10.遍历字符串s2
        for(int j = 0; j < strlen(s2); j++)
        {
            //11.判断相应字符是否相等
            if(s1[i] == s2[j])
            {
                //12.如果对应字符相等，则在二维数组对应坐标赋值为1
                a[i][j] = 1;
            }
            //13.如果对应字符不相等，则在二维数组对应坐标赋值为0
            else
                a[i][j] = 0;
        }
    }
    //14.打印说明
    printf("------------上方为输入数据-----------\n");
    printf("----------下方为二维数组数据-----------\n");
    //15.遍历输出二维数组（此处作为查看使用）
    for(int i = 0; i < strlen(s1); i++)
    {
        for(int j = 0; j < strlen(s2); j++)
        {
            printf("%d ",a[i][j]);
        }
        //16.每打印完一行，换行
        printf("\n");
    }
    //17.打印说明（分隔符）
    printf("----------下方为结果数据-----------\n");
    //18.遍历二维数组的行元素
    for(int i = 0; i < strlen(s1); i++)
    {
        //19.遍历二维数组的列元素
        for(int j = 0; j < strlen(s2); j++)
        {
            //20.判断该坐标处值是否为1，值为1代表是两个字符串开始字符开始相等的位置
            if(a[i][j] == 1)
            {
                //21.定义并初始化临时变量，记录存放公共字符串长度
                int temp = 0;
                //22.定义新的变量，存放i值，避免更改i值
                int i1 = i;
                //23.定义新的变量，存放j值，避免更改j值
                int j1 = j;
                //24.当该坐标的值为1时，进入循环，判断该坐标右下角坐标是否为1，如果为1，代表两个字符串下一个字符也相等
                while(a[i1][j1] == 1)
                {
                    //25.自增1，为下次判断做准备
                    i1++;
                    //26.自增1，为下次判断做准备
                    j1++;
                    //27.记录公共字符串的长度
                    temp++;
                }
                //28.判断新的公共字符串长度是否大于上一次公共字符串长度，如果不大于，则互换值。保证所取公共字符串的长度是最大。
                if(temp > MaxLenth)
                {
                    MaxLenth = temp;
                    //29.把最长公共字符串地址赋值给adds
                    adds = j1;
                }
            }
        }
    }
    //30.输出最大公共字符串长度值
    printf("最大公共字符串长度：%d\n",MaxLenth);
    //31.输出标题
    printf("最大公共字符串是：");
    //32.循环输出公共字符串
    for(int i = 0 ; i < MaxLenth; i++)
    {
        //33.因为所取地址值是最后的地址，所以要提取公共字符串的首字符地址，为 adds - MaxLenth
        printf("%c",s2[adds - MaxLenth + i]);
    }
    //34.输入换行符
    printf("\n");
    return 0;
}
复制代码
请输入第一个字符串：
nbitheimanb
请输入第二个字符串
itheia
------------上方为输入数据-----------
----------下方为二维数组数据-----------
0 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 1 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
1 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
----------下方为结果数据-----------
最大公共字符串长度：5
最大公共字符串是：ithei
复制代码
上面是代码，下面是运行结果。
此理论是根据，二维数组，存放0，1，对于字符串中的某个字符，把它s1位置作为横坐标，把它s2的位置作为纵坐标，在二维数组里面赋值。如果相等，赋值为1，如果不相等，赋值为0。在例子中可以看到，二维数组输出的结果。然后用for循环遍历二维数组，找出值为1的元素，当找到这个元素时，接着判断该元素的右下角的元素是否为1，如果为1，则计数，直到不为1退出。这步的作用，就是判断公共字符串的个数，至于怎么来判断的，大家可以看数组，顺序必须得时由左上角到右下角的斜线上相同为1，不能是其它的方向。看数组可以看到2、3、4、5、6行（首行为0行）对应的0、1、2、3、4列，值为1。那么在数组s1中的2、3、4、5、6号元素，和s2的0、1、2、3、4号元素就是公共字符串。如此判断，找出最长的一个，用adds记录最后一位元素的横坐标或者是纵坐标，在这里我记录的是纵坐标也就是s2数组元素序号。输出的时候注意，记录的时最后一位元素序号，所以要减去该字符长度，才是公共字符串首元素的序号。然后循环输出。
作者: a_skting    时间: 2016-6-3 08:49
{:2_32:}{:2_40:}

Snip20160603_8.png (151.81 KB, 下载次数: 7)

寻找公共子串

寻找公共子串
作者: jdc123    时间: 2016-6-3 17:51
这个必须要顶啊，虽然略显复杂，但是自己的思想，把数组和循环都用的很充分，值得研究，有利于系统理解C语言数组和循环



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