今天给各位分享c语言求连续公共子串长度的知识，其中也会对多个字符串最长公共子串进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
1、求两个输入的字符串的最长公共子串2、C语言 最长公共子串3、C语言实现最长公共子串与最长公共子序列
求两个输入的字符串的最长公共子串
算法：求两个字符串的最长公共子串
原理：
（1） 将连个字符串分别以行列组成一个矩阵。
（2）。若该矩阵的节点对应的字符相同，则该节点值为1。
（3）当前字符相同节点的值 = 左上角(d[i-1, j-1])的值 +1，这样当前节点的值就是最大公用子串的长。
(s2) b c d e
(s1)
a 0 0 0 0
b 1 0 0 0
c 0 2 0 0
d 0 0 3 0
3. 结果：只需以行号和最大值为条件即可截取最大子串
C# code:
[csharp] view plaincopyprint?
public static string MyLCS(string s1, string s2)
{
if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
{
return null;
}
else if (s1 == s2)
{
return s1;
}
int length = 0;
int end = 0;
int[,] a = new int[s1.Length, s2.Length];
for (int i = 0; i s1.Length; i++)
{
for (int j = 0; j s2.Length; j++)
{
int n = (i – 1 = 0 j – 1 = 0) ? a[i – 1, j – 1] : 0;
a[i, j] = s1[i] == s2[j] ? 1+n : 0;
if (a[i, j] length)
{
length = a[i,j];
end = i;
}
}
}
return s1.Substring(end – length + 1, length);
}
C语言 最长公共子串
首先指出楼主的错误
最长的公共子字符串 应该改成 最长的连续公共子字符串
下面是符合楼主要求的参考代码
//作者:baihacker
//时间:9.12.2006
#include stdio.h
#include string.h
void main()
{
char* x=”aabcdababce”;
char* y=”12abcabcdace”;
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用来判断是否匹配的变量
for (i=1;i=n;i++)//匹配长度的循环
for (j=0;jn-i+1;j++)//y的起始位置的循环
for (k=0;km-i+1;k++)//x的起始位置的循环
{
count = 0;
for (l=0;li;l++)//判断是否匹配,代码可以优化
if (y[j+l] == x[k+l])
count++;
if (count==iimaxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}
//作者:baihacker
//时间:9.12.2006
#include stdio.h
#include string.h
void main()
{
char* x=”aabcdababce”;
char* y=”12abcabcdace”;
int m = strlen(x);
int n = strlen(y);
int i, j, k, l;
int maxlength = 0;
int start = 0;
int count = 0;//用来判断是否匹配的变量
for (i=1;i=n;i++)//匹配长度的循环
for (j=0;jn-i;j++)//y的起始位置的循环
for (k=0;km-i;k++)//x的起始位置的循环
{
count = 0;
for (l=0;li;l++)//判断是否匹配,代码可以优化
if (y[j+l] == x[k+l])
count++;
if (count==iimaxlength)
{
maxlength = i;//记录最大长度
start = j;//记录最大长度的起起位置
}
}
if (maxlength==0)
printf(“No Answer”);
else
for (i=0;imaxlength;i++)
printf(“%c”,y[start+i]);
}
}
下面是真正的最长公共子串的动态规划算法
//作者:baihacker
//时间:9.12.2006
#include stdio.h
#include string.h
int b[50][50];
int c[50][50];
void lcs(x,m,y,n)
char *x;
int m;
char *y;
int n;
{
int i;
int j;
for (i=1;i=m;i++) c[i][0] = 0;
for (i=1;i=n;i++) c[0][i] = 0;
c[0][0] = 0;
for (i=1;i=m;i++)
for (j=1;j=n;j++)
{
if (x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else
if (c[i-1][j] c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
void show(i,j,x)
int i;
int j;
char* x;
{
if (i==0||j==0)
return;
if (b[i][j]==1)
{
show(i-1,j-1,x);
printf(“%c”,x[i-1]);
}
else
if (b[i][j]==2)
show(i-1,j,x);
else
show(i,j-1,x);
}
void main()
{
char* x=”aabcdababce”;
char* y=”12abcabcdace”;
int m = strlen(x);
int n = strlen(y);
lcs(x,m,y,n);
show(m,n,x);
}
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语言求连续公共子串长度和多个字符串最长公共子串的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
微信扫一扫 
支付宝扫一扫 
