C语言求解最长公共子字符串问题及相关的算法分析_C 语言

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子序列，并打印出最长公共子序列。
例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子序列，则输出它们的长度4，并打印任意一个子序列。
分析：求最长公共子序列（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像MicroStrategy都把它当作面试题。

完整介绍动态规划将需要很长的篇幅，因此我不打算在此全面讨论动态规划相关的概念，只集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉，请参考相关算法书比如算法讨论。

考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质：

（1） 如果am-1==bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；

（2） 如果am-1!=bn-1，则若zk-1!=am-1时，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；

（3） 如果am-1!=bn-1，则若zk-1!=bn-1时，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。

这样，在找A和B的公共子序列时，如果有am-1==bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。

求解：
引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定输出最长公共字串时搜索的方向。
我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] == Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。

问题的递归式写成：

回溯输出最长公共子序列过程：    

算法分析：
由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。

完整的实现代码如下：

/**
找出两个字符串的最长公共子序列的长度
** author :liuzhiwei
** data  :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2, int **b)
{
  int i,j,length1,length2,len;
  length1 = strlen(str1);
  length2 = strlen(str2); 

  //双指针的方法申请动态二维数组
  int **c = new int*[length1+1];   //共有length1+1行
  for(i = 0; i < length1+1; i++)
    c[i] = new int[length2+1];   //共有length2+1列 

  for(i = 0; i < length1+1; i++)
    c[i][0]=0;    //第0列都初始化为0
  for(j = 0; j < length2+1; j++)
    c[0][j]=0;    //第0行都初始化为0 

  for(i = 1; i < length1+1; i++)
  {
    for(j = 1; j < length2+1; j++)
    {
      if(str1[i-1]==str2[j-1])  //由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-1个元素
      {
        c[i][j]=c[i-1][j-1]+1;
        b[i][j]=0;     //输出公共子串时的搜索方向
      }
      else if(c[i-1][j]>c[i][j-1])
      {
        c[i][j]=c[i-1][j];
        b[i][j]=1;
      }
      else
      {
        c[i][j]=c[i][j-1];
        b[i][j]=-1;
      }
    }
  }
  /*
  for(i= 0; i < length1+1; i++)
  {
  for(j = 0; j < length2+1; j++)
  printf("%d ",c[i][j]);
  printf("\n");
  }
  */
  len=c[length1][length2];
  for(i = 0; i < length1+1; i++)  //释放动态申请的二维数组
    delete[] c[i];
  delete[] c;
  return len;
}
void PrintLCS(int **b, char *str1, int i, int j)
{
  if(i==0 || j==0)
    return ;
  if(b[i][j]==0)
  {
    PrintLCS(b, str1, i-1, j-1);  //从后面开始递归，所以要先递归到子串的前面，然后从前往后开始输出子串
    printf("%c",str1[i-1]);    //c[][]的第i行元素对应str1的第i-1个元素
  }
  else if(b[i][j]==1)
    PrintLCS(b, str1, i-1, j);
  else
    PrintLCS(b, str1, i, j-1);
} 

int main(void)
{
  char str1[100],str2[100];
  int i,length1,length2,len;
  printf("请输入第一个字符串：");
  gets(str1);
  printf("请输入第二个字符串：");
  gets(str2);
  length1 = strlen(str1);
  length2 = strlen(str2);
  //双指针的方法申请动态二维数组
  int **b = new int*[length1+1];
  for(i= 0; i < length1+1; i++)
    b[i] = new int[length2+1];
  len=LCSLength(str1,str2,b);
  printf("最长公共子序列的长度为：%d\n",len);
  printf("最长公共子序列为：");
  PrintLCS(b,str1,length1,length2);
  printf("\n");
  for(i = 0; i < length1+1; i++)  //释放动态申请的二维数组
    delete[] b[i];
  delete[] b;
  system("pause");
  return 0;
}

程序的效果图如下：

第二种方法为：

/**
找出两个字符串的最长公共子序列的长度
** author :liuzhiwei
** data  :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2)  //求得两个字符串的最大公共子串长度并输出公共子串
{
  int i,j,length1,length2;
  length1 = strlen(str1);
  length2 = strlen(str2); 

  //双指针的方法申请动态二维数组
  int **c = new int*[length1+1];   //共有length1+1行
  for(i = 0; i < length1+1; i++)
    c[i] = new int[length2+1];   //共有length2+1列 

  for(i = 0; i < length1+1; i++)
    c[i][0]=0;    //第0列都初始化为0
  for(j = 0; j < length2+1; j++)
    c[0][j]=0;    //第0行都初始化为0 

  for(i = 1; i < length1+1; i++)
  {
    for(j = 1; j < length2+1; j++)
    {
      if(str1[i-1]==str2[j-1])  //由于c[][]的0行0列没有使用，c[][]的第i行元素对应str1的第i-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];
    }
  } 

  //输出公共子串
  char s[100];
  int len,k;
  len=k=c[length1][length2];
  s[k--]='\0';
  i=length1,j=length2;
  while(i>0 && j>0)
  {
    if(str1[i-1]==str2[j-1])
    {
      s[k--]=str1[i-1];
      i--;
      j--;
    }
    else if(c[i-1][j]<c[i][j-1])
      j--;
    else
      i--;
  }
  printf("最长公共子串为：");
  puts(s); 

  for(i = 0; i < length1+1; i++)  //释放动态申请的二维数组
    delete[] c[i];
  delete[] c;
  return len;
} 

int main(void)
{
  char str1[100],str2[100];
  int length1,length2,len; 

  printf("请输入第一个字符串：");
  gets(str1);
  printf("请输入第二个字符串：");
  gets(str2);
  length1 = strlen(str1);
  length2 = strlen(str2);
  len=LCSLength(str1,str2);
  printf("最长公共子串的长度为：%d\n",len);
  system("pause");
  return 0;
}

       问题拓展：设A、B、C是三个长为n的字符串，它们取自同一常数大小的字母表。设计一个找出三个串的最长公共子序列的O(n^3)的时间算法。
       思路：跟上面的求2个字符串的公共子序列是一样的思路，只不过这里需要动态申请一个三维的数组，三个字符串的尾字符不同的时候，考虑的情况多一些而已。

/**
找出三个字符串的最长公共子序列的长度
** author :liuzhiwei
** data  :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int max1(int m,int n)
{
  if(m>n)
    return m;
  else
    return n;
}
int max2(int x,int y,int z,int k,int m,int n)
{
  int max=-1;
  if(x>max)
    max=x;
  if(y>max)
    max=y;
  if(z>max)
    max=z;
  if(k>max)
    max=k;
  if(m>max)
    max=m;
  if(n>max)
    max=n;
  return max;
}
int LCSLength(char* str1, char* str2, char* str3)  //求得三个字符串的最大公共子序列长度并输出公共子序列
{
  int i,j,k,length1,length2,length3,len;
  length1 = strlen(str1);
  length2 = strlen(str2);
  length3 = strlen(str3); 

  //申请动态三维数组
  int ***c = new int**[length1+1];   //共有length1+1行
  for(i = 0; i < length1+1; i++)
  {
    c[i] = new int*[length2+1];   //共有length2+1列
    for(j = 0; j<length2+1; j++)
      c[i][j] = new int[length3+1];
  } 

  for(i = 0; i < length1+1; i++)
  {
    for(j = 0; j < length2+1; j++)
      c[i][j][0]=0;
  }
  for(i = 0; i < length2+1; i++)
  {
    for(j = 0; j < length3+1; j++)
      c[0][i][j]=0;
  }
  for(i = 0; i < length1+1; i++)
  {
    for(j = 0; j < length3+1; j++)
      c[i][0][j]=0;
  } 

  for(i = 1; i < length1+1; i++)
  {
    for(j = 1; j < length2+1; j++)
    {
      for(k = 1; k < length3+1; k++)
      {
        if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1])
          c[i][j][k]=c[i-1][j-1][k-1]+1;
        else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1])
          c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]);
        else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1])
          c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]);
        else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1])
          c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]);
        else
        {
          c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]);
        }
      }
    }
  }
  len=c[length1][length2][length3];
  for(i = 1; i < length1+1; i++)     //释放动态申请的三维数组
  {
    for(j = 1; j < length2+1; j++)
      delete[] c[i][j];
    delete[] c[i];
  }
  delete[] c;
  return len;
} 

int main(void)
{
  char str1[100],str2[100],str3[100];
  int len; 

  printf("请输入第一个字符串：");
  gets(str1);
  printf("请输入第二个字符串：");
  gets(str2);
  printf("请输入第三个字符串：");
  gets(str3);
  len=LCSLength(str1,str2,str3);
  printf("最长公共子序列的长度为：%d\n",len);
  system("pause");
  return 0;
}

程序的效果图如下：

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c语言
， 算法
字符串
c语言输出最长字符串、c语言找最长的字符串、c语言字符串加密算法、c语言字符串匹配算法、c语言 字符串压缩算法，以便于您获取更多的相关知识。

时间： 2024-08-01 16:53:43

C语言求解最长公共子字符串问题及相关的算法分析_C 语言的相关文章

使用C语言求解扑克牌的顺子及n个骰子的点数问题_C 语言

扑克牌的顺子    问题描述:从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的.2-10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以看成任意数字.          思路:可以将这5张牌排个序,然后统计出0的个数以及非0数字之间的间隔数,如果出现重复的非0数字,那么不是顺子.如果间隔数小于等于0的个数,那么是顺子.暂时未想到更好的办法.          参考代码: //函数功能 : 从扑克牌中随机抽5张牌,判断是不是一个顺子 //函数参数 : pCards为

算法-求助大神：c语言求最长公共子序列问题

问题描述 求助大神:c语言求最长公共子序列问题 我写的这个能正确求出最长序列元素个数但是输出的最长序列却是乱码,求大神指教.代码如下: #include #include #include #define MAX 101 int Long(char a[],char b[],char result[] ) { int m,n; m=strlen(a); n=strlen(b); int str[MAX][MAX]; int i,j,sum; for(i=0;i<=m;i++) { str[i][

一些C语言中字符串的算法问题解决实例小结_C 语言

    字符串问题是面试中经常出现的问题,这类问题有很多,难以不一.下面是几道字符串的题目,网上都能找到解答,自己实现了一下,供网友参考.感觉算法重要的是要有正确的思路,实现起来不是问题.自己一定要多思考,这样收获可能会更多一点.         问题1:找两个字符串的最长公共子串.         具体描述,如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字

c字符串,string对象,字符串字面值的区别详解_C 语言

一.字符串字面值字符串字面值是一串常量字符,字符串字面值常量用双引号括起来的零个或多个字符表示,为兼容C语言,C++中所有的字符串字面值都由编译器自动在末尾添加一个空字符.字符串没有变量名字,自身表示自身 复制代码 代码如下: "Hello World!" //simple string literal"" //empty string literal"\nCC\toptions\tfile.[cC]\n" //string literal us

C语言实现输入一个字符串后打印出该字符串中字符的所有排列_C 语言

本文实例讲述了C语言实现输入一个字符串后打印出该字符串中字符的所有排列的方法,属于数学里的排列问题.是一个很实用的算法技巧.分享给大家供大家参考.具体实现方法如下: 例如输入字符串abc,则输出由字符a.b.c所能排列出来的所有字符串abc.acb.bac.bca.cab和cba. C语言实现代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <al

C语言字符串操作总结大全(超详细)_C 语言

1)字符串操作 strcpy(p, p1) 复制字符串 strncpy(p, p1, n) 复制指定长度字符串 strcat(p, p1) 附加字符串 strncat(p, p1, n) 附加指定长度字符串 strlen(p) 取字符串长度 strcmp(p, p1) 比较字符串 strcasecmp忽略大小写比较字符串strncmp(p, p1, n) 比较指定长度字符串 strchr(p, c) 在字符串中查找指定字符 strrchr(p, c) 在字符串中反向查找 strstr(p, p1

C语言实现基于最大堆和最小堆的堆排序算法示例_C 语言

堆定义堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其自身

C++三色球问题描述与算法分析_C 语言

本文实例讲述了C++三色球问题.分享给大家供大家参考,具体如下: /* * 作 者:刘同宾 * 完成日期:2012 年 11 月 15 日 * 版 本 号:v1.0 * * 输入描述: * 问题描述:三色球问题:若一个口袋中放有12个球,其中有3个红的.3个白的和6个黒的,问从中任取8个共有多少种不同的颜色搭配? * 提示: 设任取的红球个数为i,白球个数为j,则黒球个数为8-i-j,根据题意红球和白球个数的取值范围是0~3, * 在红球和白球个数确定的条件下,黒球个数取值应为8-i-j<=6.

C语言中一些将字符串转换为数字的函数小结_C 语言

C语言atoi()函数:将字符串转换成int(整数)头文件: #include <stdlib.h> atoi() 函数用来将字符串转换成整数(int),其原型为: int atoi (const char * str); [函数说明]atoi() 函数会扫描参数 str 字符串,跳过前面的空白字符(例如空格,tab缩进等,可以通过 isspace() 函数来检测),直到遇上数字或正负符号才开始做转换,而再遇到非数字或字符串结束时('\0')才结束转换,并将结果返回. [返回值]返回转换后的整