最长公共子字符串的使用分析__curmax_max_Substring_s1_start_s2_start_

当前位置: 编程技术>c/c++/嵌入式

最长公共子字符串的使用分析

来源: 互联网发布时间：2014-10-15

本文导语: 子字符串的定义和子串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2。最长公共子字符串共有两种解决方法，下面具体说说我的思路方法一：Lon...

子字符串的定义和子串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2。
最长公共子字符串共有两种解决方法，下面具体说说我的思路
方法一：
Longest Common Substring和Longest Common Subsequence是有区别的
X =
Y =
X和Y的Longest Common Sequence为，长度为4
X和Y的Longest Common Substring为长度为2
其实Substring问题是Subsequence问题的特殊情况，也是要找两个递增的下标序列
和使
xi1 == yj1
xi2 == yj2
......
xik == yjk
与Subsequence问题不同的是，Substring问题不光要求下标序列是递增的，还要求每次
递增的增量为1，即两个下标序列为：
和
类比Subquence问题的动态规划解法，Substring也可以用动态规划解决，令
c[i][j]表示Xi和Yi的最大Substring的长度，比如
X =
Y =
c[1][1] = 1
c[2][2] = 2
c[3][3] = 0
c[4][4] = 1
动态转移方程为：
如果xi == yj，则 c[i][j] = c[i-1][j-1]+1
如果xi ! = yj, 那么c[i][j] = 0
最后求Longest Common Substring的长度等于
max{ c[i][j], 1 max ? curmax : max;
    curmax = 0;
   }
  }
  max = curmax > max ? curmax : max;
}
return max;
}
int main(void)
{
char str1[1000],str2[1000];
printf("请输入第一个字符串：");
gets(str1);
printf("请输入第二个字符串：");
gets(str2);
int len = longest_common_substring(str1, str2);
printf("最长公共连续子串的长度为：%dn",len);
system("pause");
return 0;
}

效果图如下：

稍微改动一下，便可以输出公共子串了，就是要保存一下连续公共子串最后一个字符在其中一个字符串中的下标位置：

代码如下:

/** 
找出两个字符串的最长公共连续子串的长度
** author :liuzhiwei  
** data   :2011-08-16
**/ 
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
 int i,k,len1,len2,len,s1_start,s2_start,idx,curmax,max;
 len1 = strlen(str1);
 len2 = strlen(str2);
 len = len1 + len2;
 max = 0;
 for(i = 0 ; i < len ; i++)
 {
  s1_start = s2_start = 0;
  if(i < len1)
   s1_start = len1 - i;    //每次开始匹配的起始位置
  else
   s2_start = i - len1;
  curmax = 0;
  for(idx = 0 ; ( s1_start + idx < len1 ) && ( s2_start + idx < len2 ); idx++ )
  {
   if(str1[s1_start+idx]==str2[s2_start+idx])
    curmax++;
   else     //只要有一个不相等，就说明相等的公共字符断了，不连续了，要保存curmax与max中的最大值，并将curmax重置为0
   {
    //max = curmax > max ? curmax : max;
    if(curmax > max)
    {
     max = curmax;
     k = s1_start+idx-1;      //保存连续子串长度增加时连续子串最后一个字符在str1字符串中的下标位置，便于输出公共连续子串
    }
    curmax = 0;
   }
  }
  //max = curmax > max ? curmax : max;
  if(curmax > max)
  {
   max = curmax;
   k = s1_start+idx-1;
  }
 }
 //输出公共子串
 char s[1000];
 for(i=0;i