求两个字符串的最长公共子串.docVIP

求两个字符串的最长公共子串(LCS) 最长公共子串(LCS),有三种情况:1.公共子串的元素必须相邻. 2.公共子串的元素可以不相邻联单3. 求多个字符串而不是两个字符串的最长公共子串 1.公共子串的元素必须相邻: ??? LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置. 下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232??????0 0 0 1 0 0 0 1 1 0 0 1 0 0 0　　? 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0　? 　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0　? 　0 1 0 0 0 0 0 0 0 1 1 0 0 0 0　? 　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0　? 　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0　　? 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0　? 　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0　? 　0 0 0 1 0 0 0 1 1 0 0 1 0 0 0　? 　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0　? 　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0　? 　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0　? 　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0??? 但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方式： ?????0 0 0 1 0 0 0 1 1 0 0 1 0 0 0　　? 0 1 0 0 0 0 0 0 0 2 1 0 0 0 0　? 　1 0 2 0 1 0 1 0 0 0 0 0 1 0 0　? 　0 2 0 0 0 0 0 0 0 1 1 0 0 0 0　? 　1 0 3 0 1 0 1 0 0 0 0 0 1?0 0　? 　0 0 0 4 0 0 0 2 1 0 0 1 0 0 0　　? 1 0 1 0 5 0 1 0 0 0 0 0 2 0 0　? 　1 0 1 0 1 0 1 0 0 0 0 0 1 0 0　? 　0 0 0 2 0 0 0 2 1 0 0 1 0 0 0　? 　0 0 0 0 0 0 0 0 0 0 0 0 0 1 0　　? 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0　? 　0 0 0 0 0 1 0 0 0 0 0 0 0 0 0　? 　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0??? 当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。 ? 算法的基本思想： 当字符匹配的时候，不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。 我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断 当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时 候，最长匹配子串的位置和长度就已经出来了。 =========================================================================== 程序： #includestring.h #define M 100 char* LCS(char left[],char right[]) {??? //LCS问题就是求两个字符串最长公共子串的问题 ??? int lenLeft=strlen(left),lenRight=strlen(right),k; ??? //获取左子串的长度,获取右子串的长度 ??? char*c=malloc(lenRight),*p;//注意这里要写成char型,而不是int型,否则输入整型数据时会产生错误。????? //矩阵c纪录两串的匹配情况 //int c[M][M]={0};//当将c申明为一个二维数组时 ??? int start,end,len,i,j;//start表明最长公共子串的起始点，end表明