找出多个字符串中的最大公共子字符串，如“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数组元素序号。输出的时候注意，记录的时最后一位元素序号，所以要减去该字符长度，才是公共字符串首元素的序号。然后循环输出。
|
|
收藏
淘帖
踩
