本篇文章给大家谈谈c语言求最长公共子串，以及c最长公共子串算法对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
1、C语言实现最长公共子串与最长公共子序列2、如何使用C语言求解最长公共子字符串问题及相关的算法3、c语言求最长公共子串长度4、C语言：“最长公共子串” 高手帮忙编个
C语言实现最长公共子串与最长公共子序列
给定两个字符串s1=”GeeksforGeeks”，s2=”GeeksQuizGo”，则它们的最长公共子串为“Geeks”，长度为5。
运用动态规划的思想，将两个字符串映射为一张二维表，表格中的值代表到当前为止的最长公共子串的值，如下图所示：
生成这张表的步骤（假设这张表为t[][], r为行标，c为列标）：
Code
整个算法的时间复杂度为O(len1 * len2)，len1与len2分别为两个字符串的长度。
最长公共子序列与最长公共子串的区别是，最长公共子序列不要求“连续匹配”，它的目的是找到两个字符串中最大的公共部分。依然以s1=”GeeksforGeeks”，s2=”GeeksQuizGo”为例，它们的最长公共子序列为“Geekso”和“GeeksG”，长度为6。
它的二维表如下所示：
它的生成步骤与最长公共子序列的最大不同在第3步，最长公共子序列在遇到s1[r] != s2[c]情况时，不会将t[r][c]重置为0，而是选择Max(t[r-1][c], t[r][c-1])作为新值，即它一直保存着前面已比较序列的最长公共序列值。
如何使用C语言求解最长公共子字符串问题及相关的算法
假定字符串采用堆分配方式，编写一个程序，求两个字符串S和T的一个最长公共子串
本题的思路：
本题要实现的算法扫描两个字符串。其中index指出最长公共子串在s中的序号，length指出最长公共子串的长度
堆分配存储表示如下：
typedef struct{
char *ch;
int length;
}Hstring;
Status MaxComString(Hstring S,Hstring T,int length){
index=0;
length=0;
i=0;
//令i作为扫描字符串S的指针
while(iS.length){
j=0;
//令j作为扫描字符串T的指针
while(jT.length){
if(s.ch[i]==T.ch[j]){
//找一个子串，其在字符串S中的序号为i，长度为length1
length1=i;
for(k=1;S.ch[i+k]==T.ch[j+k];k++)length1++;
if(length1length){
//将较大长度值赋给index与length
index=i;
length=length1;
}
j=j+length1;//继续扫描字符串T中第j=length1个字符之后的字符
}else{
j++;
}
}//while
i++;
}//while
printf(“最长公共子串:”);
for(i=0;ilength;i++)printf(“%c”,S.ch[index+i]);
return OK;
}
c语言求最长公共子串长度
将两个字符串组成二维数组，相同的值为1，不同的值为0，同时在对角线上叠加，矩阵中的最大值则为最长公共子串长度.
########3.编译源码
C语言：“最长公共子串” 高手帮忙编个
描述]
现在有一些由英文字符组成的大小写敏感的字符串，你的任务是找到一个最长的字符串[x]，使得对于已经给出的字符串中的任意一个y，[x]或[反序后的x]是y的子串。
[关于输入]
输入的第一行是一个整数t (1 = t = 10)，t表示测试数据的数目。对于每一组测试数据，第一行是一个整数n (1 = n = 100)，表示已经给出n个字符串。接下来n行，每行给出一个长度在1和100之间的字符串。
[关于输出]
对于每一组测试数据，输出一行，给出题目中要求的字符串x的长度。
c语言求最长公共子串的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于c最长公共子串算法、c语言求最长公共子串的信息别忘了在本站进行查找喔。
微信扫一扫 
支付宝扫一扫 
