题目:给出两个字符串,找出这两个字符串的公共子字符串。
公共子字符串和公共序列不同的地方在于 公共子字符串要求子串在两个字符串中必须是连续的。
例如:“123579” 和 “2378”公共子字符串为“23”,公共子序列为“237”
动态转移方程为:
如果 xi==yj,则c[i][j] = c[i-1][j-1]+1;
如果xi != yj, 则c[i][j] = 0;
最后求的的长度为max{c[i][j], 1<=i<=n, 1<=j<=m};
代码如下:
//动态规划 //最长公共字串 #include<stdio.h> #include<string.h> #include<malloc.h> #include<assert.h> void Fun(char *str1, char *str2); int main() { char str1[100]; char str2[100]; printf("输入字串1\n"); gets(str1); printf("输入字串2\n"); gets(str2); Fun(str1, str2); } void Fun(char *str1, char *str2) { int length1; int length2; int **Res; int i, j; int max = 0;//公共字串的长度 int pos = 0; //公共字串结束的位置 length1 = strlen(str1); length2 = strlen(str2); Res = (int **)malloc(sizeof(int *) * (length1+1)); assert(Res != NULL); for(i = 0; i < length2+1; ++i) { Res[i] = (int *)malloc(sizeof(int) * (length2 + 1)); assert(Res[i] != NULL); } for(i = 0; i < length1+1; ++i) Res[i][0] = 0; for(j = 0;j < length2+1; ++j) Res[0][j] = 0; for(i = 1; i < length1+1; ++i) { for(j = 1; j < length2+1; ++j) { if(str1[i-1] == str2[j-1]) { Res[i][j] = Res[i-1][j-1] + 1; } else Res[i][j] = 0; } } for(i = 0; i < length1+1; ++i) //观察结果 { for(j = 0; j< length2+1; ++j) printf("%2d ", Res[i][j]); printf("\n"); } for(i = 0; i < length1+1; ++i) for(j = 0; j < length2 + 1; ++j) { if(max < Res[i][j]) { max = Res[i][j]; pos = i; } } printf("最长公共字串的长度为%d %d\n", max,pos); for(i = pos-max; i < pos; ++i) printf("%c", str1[i]); for(i = 0; i < length1+1; ++i) free(Res[i]); }