找固定长度的公共子串
本帖最后由 hisweetgirl 于 2013-09-06 16:25:58 编辑 比如三字符串，abcdef,abgdel，dhabfgde 找出长度为2的公共子串，有ab,de,怎么找出所有的公共子串呢
[解决办法]
1. 拿第一个串做为源串。
2. 当前位置＝源串的第一个字符位置
3. 从源串的当前位置取两个字符，和目标串（第二和第三串）中进行查找，如果都找到就是公共子串。
4. 当前位置往右移一个字符，跳到第3步
大概思路就这样，具体的自己再细化一下
[解决办法]
//最长公共子序列字符个数
//c[i][j]保存字符串 {xi},{yj},(长度分别为i,j)的最长公共子序列的字符个数
//i=0或者是j=0 时，c[i][j]必定为零, i,j>=0 且 xi=yj, c[i][j]=c[i-1][j-1]+1
//若 i,j>0 但xi!=yj, c[i][j]=max{ c[i-1][j] , c[i][j-1] }
#include <stdio.h>
#include <string.h>
int c[1001][1001];
void lcs(int a, int b, char x[], char y[], int c[][1001]) {
int i,j;
for(i=1;i<a;i++)
c[i][0]=0; //if b==0, set c[i][j]=0;
for(i=1;i<b;i++)
c[0][i]=0; // if a==0; set c[i][j]=0;
for(i=1;i<=a;i++) // if a!=0,b!=0 loop
for(j=1;j<=b;j++) {
if(x[i-1]==y[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}
int main() {
char x[1001],y[1001];
while ( scanf("%s%s",x,y)!=EOF ) {
int a=strlen(x);
int b=strlen(y);
memset(c,0,sizeof(c));
lcs(a,b,x,y,c);
printf("%d\n",c[a][b]);
}
return 0;
}
