最長公共子串c語言-九游会j9娱乐平台

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

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

{

for(intj=0;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
#include

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 for (k=0;k {
count = 0;
for (l=0;l if (y[j l] == x[k l])
count ;
if (count==i&&i>maxlength)
{
maxlength = i;//璁板綍鏈澶ч暱搴
start = j;//璁板綍鏈澶ч暱搴︾殑璧瘋搗浣嶇疆
}
}

//浣滆:hacker
//鏃墮棿:9.12.2006
#include
#include

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 for (k=0;k {
count = 0;
for (l=0;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 printf("%c",y[start i]);
}

}
涓嬮潰鏄鐪熸ｇ殑鏈闀垮叕鍏卞瓙涓茬殑鍔ㄦ佽勫垝綆楁硶
//浣滆:hacker
//鏃墮棿:9.12.2006

#include
#include

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);

}