求两个输入的字符串的最长公共子串
算法：求两个字符串的最长公共子串
原理：
（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语言实现最长公共子串与最长公共子序列
给定两个字符串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语言编程 查找两字符串的最长公共子串 如”I am a student.”与”R u a student?”最长公共子串是”student”
//有个问题是,空格应该也算字符吧，所以没考虑空格。就像你那个例子，最长公共字串应该是//“ student”,包含空格.还有,就是我这个应该不是很好的方法，效率比较低，我是先让串//1不动，串2先从第1个字符开始与串1比较，然后串2从第2个字符开始于串1比较，都比较完了，///串1向右挪动一个位置
#includestdio.h
int main()
{
char str1[100]={0},str2[100]={0};
printf(“please input two strings:\n”);
gets(str1);//读入字串
gets(str2);
char * p1=str1;//分别用来存str1和str2的当下比较位置
char * p2=str2;
int max=0,num=0;//max存放比较后最长字串长度，num是这一轮比较公共字串长度
char * start;//存放最大串起始位置
while(*p1!=’\0′)//先是串1大循环
{
p2=str2; //p2是串2首地址
while(*p2!=’\0′)
{
char * begin=p1;//begin是串1当前比较位置
char * begin2=p2;//begin2是串2开始比较位置
num=0;//比较前初始化为0
while(*begin!=’\0′ *begin2!=’\0′)//一轮新的比较
{
if(*begin==*begin2) //若相同，num++；
{num++;begin++;begin2++;}
else break;
}
if(nummax) //若新比较出的字串更长，则替换max值和start内容
{max=num;
start=p1;}
p2++; //串2右移1位
}
p1++; //串1右移1位
}
while(max–) //输出串
printf(“%c”,*start++);
printf(“\n”);
}
c语言求最长公共子串长度
将两个字符串组成二维数组，相同的值为1，不同的值为0，同时在对角线上叠加，矩阵中的最大值则为最长公共子串长度.
########3.编译源码
C语言 求最长公共子串的代码，其中有一句j+=length1;不太明白作用是什么，没有这句有什么影响，望解答
这个算法是错误的，代码中有一些错误，我修改如下：
j+=length的原始意图是想让s[i]==t[j]满足的情况下，将t字符串移动。
但为什么能一下移动length这么长？这样虽然程序不会死循环，但结果不对。
由于一下子移动太多，可能会漏掉真正的最长公共子串，比如下面这个例子：
#include stdio.h
#include string.h
void MaxComStr_youError(char s[],char t[],char c[])
{
int index=0,length=0,i,j,k,length1;
i=0;
while(s[i]!=’\0′)
{
j=0;
while(t[j]!=’\0′)
{
if(s[i]==t[j])
{
length1=1;
for(k=1 ; i+kstrlen(s) j+kstrlen(t) s[i+k]==t[j+k] ; k++)
length1++;
if(length1length)
{
index=i;
length=length1;
}
j+=length1;//这一句的作用是什么没有这一句对程序有什么影响？×/
}
else j++;
}
i++;
}
for (i=0;ilength;i++)
c[i]=s[index+i];
c[length]=’\0′;
}
void MaxComStr_OK(char s[],char t[],char c[])
{
int index=0,length=0,i,j,k,length1;
i=0;
while(s[i]!=’\0′)
{
j=0;
while(t[j]!=’\0′)
{
if(s[i]==t[j])
{
length1=1;
for(k=1 ; i+kstrlen(s) j+kstrlen(t) s[i+k]==t[j+k] ; k++)
length1++;
if(length1length)
{
index=i;
length=length1;
}
}
j++;
}
i++;
}
for (i=0;ilength;i++)
c[i]=s[index+i];
c[length]=’\0′;
}
int main(int argc, char* argv[])
{
char s[] = “xxxxxxxxababc”;
char t[]= “abababc”;
char c[100];
printf(“s=%s\r\nt=%s\r\n”,s,t);
MaxComStr_youError(s,t,c);
printf(“\r\nERROR result:%s\r\n”,c);
MaxComStr_OK(s,t,c);
printf(“OK result:%s”,c);
}
程序输出为：
s=xxxxxxxxababc
t=abababc
ERROR result:abab
OK result:ababc
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);
}
微信扫一扫 
支付宝扫一扫 
