在计算机科学中，最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。
实验目的通过解决求两个串的最大子串的问题，提升对串的理解。
实验要求用户输入两个串，实现求出这两个串的最大公共子串的操作。
实验内容和实验步骤 1.需求分析用户输入两个串，求出这两个串的最大公共子串。2. 概要设计
设计一个函数实现求最大公共子串操作，在主函数中让用户输入两个串并输出结果。3. 详细设计
导入一些库并定义最大串长和串的基本类型
#include#include #include //定义最大串长 #define MAXSIZE 81 //定义串的基本类型，顺序串 typedef struct { //包括两个东西，一个是串长另一个就是存储串的数组了 int len; char ch[MAXSIZE]; } stringtype;
求最大公共子串的函数
void comstrmax(stringtype *s, stringtype *t)
{
//求s和t的最大公共子串
int position = 0, maxlen = 0, i = 0, j, k, length;
while (i < s->len)
{
//从s的第一个字符开始，如果有匹配的子串，就记录下这个子串的长度，然后从第二个字符开始，记录比较这些长度，得到最大长度和开始的位置
j = 0;
while (j < t->len)//t有多少个字符就循环多少次
{
if (s->ch[i] == t->ch[j])
{
length = 1;//设置初始长度
for (k = 1; s->ch[i + k] == t->ch[j + k]; k++)
length++;//两个串同时往后移，如果相等长度就加一
if (length > maxlen)
{
//如果这一次是最大长度就记录下长度和i（开始匹配的位置）
position = i;
maxlen = length;
}
j += length;//这一次碰到不相等的了，但是t串后面可能还有匹配的子串，所以不能跳出循环，就让t往后移匹配的长度位
}
else
j++;//如果没有匹配的话，就往后移一位
}
i++;
}
printf("n字符串'%s'和'%s'的最大公共子串：", s->ch, t->ch);
for (i = 0; i < maxlen; i++)
printf("%c", s->ch[position + i]);
}
主函数部分
- 实现的操作就是用户输入两个串，然后调用函数输出结果。
int main() {
stringtype *str, *str1;
str = (stringtype *) malloc(sizeof(stringtype));
str1 = (stringtype *) malloc(sizeof(stringtype));
printf("输入第一个字符串:");
scanf("%s", str->ch);
str->len = strlen(str->ch);
printf("输入第二个字符串:");
scanf("%s", str1->ch);
str1->len = strlen(str1->ch);
comstrmax(str, str1);
return 0;
}
4. 调试分析
遇到的问题及解决方法
- 算法原理有一丝复杂，多看看然后举例子就理解了
这个算法比较复杂，总共有三层循环。
实验结果
实验结果很不错！
寻找最大公共子串的原理很有意思，要反复好好体会，多多重复，百炼成钢！
最后附上完整的代码
#include#include #include //定义最大串长 #define MAXSIZE 81 //定义串的基本类型，顺序串 typedef struct { //包括两个东西，一个是串长另一个就是存储串的数组了 int len; char ch[MAXSIZE]; } stringtype; void comstrmax(stringtype *s, stringtype *t) { //求s和t的最大公共子串 int position = 0, maxlen = 0, i = 0, j, k, length; while (i < s->len) { //从s的第一个字符开始，如果有匹配的子串，就记录下这个子串的长度，然后从第二个字符开始，记录比较这些长度，得到最大长度和开始的位置 j = 0; while (j < t->len)//t有多少个字符就循环多少次 { if (s->ch[i] == t->ch[j]) { length = 1;//设置初始长度 for (k = 1; s->ch[i + k] == t->ch[j + k]; k++) length++;//两个串同时往后移，如果相等长度就加一 if (length > maxlen) { //如果这一次是最大长度就记录下长度和i（开始匹配的位置） position = i; maxlen = length; } j += length;//这一次碰到不相等的了，但是t串后面可能还有匹配的子串，所以不能跳出循环，就让t往后移匹配的长度位 } else j++;//如果没有匹配的话，就往后移一位 } i++; } printf("n字符串'%s'和'%s'的最大公共子串：", s->ch, t->ch); for (i = 0; i < maxlen; i++) printf("%c", s->ch[position + i]); } int main() { stringtype *str, *str1; str = (stringtype *) malloc(sizeof(stringtype)); str1 = (stringtype *) malloc(sizeof(stringtype)); printf("输入第一个字符串:"); scanf("%s", str->ch); str->len = strlen(str->ch); printf("输入第二个字符串:"); scanf("%s", str1->ch); str1->len = strlen(str1->ch); comstrmax(str, str1); return 0; }
