最長公共子串c語言

❶ 求兩個輸入的字元串的最長公共子串

1. 演算法：求兩個字元串的最長公共子串

2. 原理：

（1） 將連個字元串分別以行列組成一個矩陣。

（2）。若該矩陣的節點對應的字元相同，則該節點值為1。

（3）當前字元相同節點的值 = 左上角(d[i-1, j-1])的值 +1，這樣當前節點的值就是最大公用子串的長。

(s2)bcde

(s1)

a0000

b1000

c0200

d0030

3. 結果：只需以行號和最大值為條件即可截取最大子串

C# code:

[csharp]view plainprint?

publicstaticstringMyLCS(strings1,strings2)

{

if(String.IsNullOrEmpty(s1)||String.IsNullOrEmpty(s2))

{

returnnull;

}

elseif(s1==s2)

{

returns1;

}

intlength=0;

intend=0;

int[,]a=newint[s1.Length,s2.Length];

for(inti=0;i<s1.Length;i++)

{

for(intj=0;j<s2.Length;j++)

{

intn=(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;

}

}

}

returns1.Substring(end-length+1,length);

}

❷ C璇璦 鏈闀垮叕鍏卞瓙涓

棣栧厛鎸囧嚭妤間富鐨勯敊璇
鏈闀跨殑鍏鍏卞瓙瀛楃︿覆 搴旇ユ敼鎴 鏈闀跨殑榪炵畫鍏鍏卞瓙瀛楃︿覆
涓嬮潰鏄絎﹀悎妤間富瑕佹眰鐨勫弬鑰冧唬鐮
//浣滆:hacker
//鏃墮棿: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;j<n-i+1;j++)//y鐨勮搗濮嬩綅緗鐨勫驚鐜
for (k=0;k<m-i+1;k++)//x鐨勮搗濮嬩綅緗鐨勫驚鐜
{
count = 0;
for (l=0;l<i;l++)//鍒ゆ柇鏄鍚﹀尮閰,浠ｇ爜鍙浠ヤ紭鍖
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//璁板綍鏈澶ч暱搴
start = j;//璁板綍鏈澶ч暱搴︾殑璧瘋搗浣嶇疆
}
}

//浣滆:hacker
//鏃墮棿: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;j<n-i;j++)//y鐨勮搗濮嬩綅緗鐨勫驚鐜
for (k=0;k<m-i;k++)//x鐨勮搗濮嬩綅緗鐨勫驚鐜
{
count = 0;
for (l=0;l<i;l++)//鍒ゆ柇鏄鍚﹀尮閰,浠ｇ爜鍙浠ヤ紭鍖
if (y[j+l] == x[k+l])
count++;
if (count==i&&i>maxlength)
{
maxlength = i;//璁板綍鏈澶ч暱搴
start = j;//璁板綍鏈澶ч暱搴︾殑璧瘋搗浣嶇疆
}
}

if (maxlength==0)
printf("No Answer");
else
for (i=0;i<maxlength;i++)
printf("%c",y[start+i]);
}

}
涓嬮潰鏄鐪熸ｇ殑鏈闀垮叕鍏卞瓙涓茬殑鍔ㄦ佽勫垝綆楁硶
//浣滆:hacker
//鏃墮棿: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);

}