当前位置：文档库 › 串的应用求两个串的最长公共子串(附答案)

串的应用求两个串的最长公共子串(附答案)

实验八《串的应用》实验-----求两个串的最长公共子串

（一）实验目的

掌握顺序串的基本操作。

（二）实验内容与要求

1、采用顺序存储结构用户输入的两个串，输出这两个串的最长公共子串

2、问题描述

先给最长公共子串的下标index和长度maxlen均赋值为0。

设s=”a0a1……a n”,t=”b0b1……b m”,扫描串s，对于当前字符a i,扫描t，若b j=a i, 计算它们其后相同字符的个数，并赋给leng,若leng>maxlen，说明它是当前最长公共子串，则index=i,然后继续扫描t，直到t完毕。当t完毕后，又继续扫描s，直到s完毕。这样s 串中从index开始的maxlen个字符构成的串便是最长子串。

（三）算法

1、数据类型定义

struct str{

char vec[MAXCHAR];

int len;

};

2、操作算法

(1)找最长公共子串算法

void maxcomstr(struct str *s, struct str *t)

{同学们自己编写

}

（2）主函数main( )

3、程序

#include

#include< iostream.h >

#include

#define MAXCHAR 30

struct str{

char vec[MAXCHAR];

int len;

};

找最长公共子串算法

void maxcomstr(struct str *s,struct str *t)

{int index=0,maxlen=0,i=0,j,k,leng;

while (ilen)

{_____________________

while (jlen)

{if (____________________________)

{ leng=1;

for (k=1;s->vec[i+k]==t->vec[j+k];k++)

_______________________

if (leng>maxlen)

{ index=i;

_________________________}

j+=leng;

}

else j++;

i++;}}

printf("\n字符串%s和%s的最长公共子串：",s->vec,t->vec); for (i=0;i

printf("%c",s->vec[index+i]);

printf("\n");

}

void main( )

{ struct str *r,*r1;

r=new str; r1=new str;

cout<<”输入第一个字符串：”;

sanf(“%s”,r->vec);

r->len=strlen(r->vec);

cout<<”输入第二个字符串：”;

sanf(“%s”,r1->vec);

r1->len=strlen(r1->vec);

maxcomstr（r,r1）;

}

（四）实验结果

1、求两个串”ababcabcdabcde”和“xyabcdxy”的最长公共子串。

2、程序执行过程：请同学们写出

3．分析程序并给出小结、体会。

答案下页

最长公共子序列问题(最)

算法作业： LCS 问题作业要求：设计一个算法求出两个序列的所有LCS ，分析最坏情况，用“会计方法”证明利用b[i][j]求出所有LCS 的算法在最坏情况下时间复杂度为)(m m n C O + 1、算法思路：根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设X={x 1, x 2, … , x n }, Y={y 1, y 2, … , y m }, 首先引入二维数组C[i][j]记录X i 和Y j 的LCS 的长度，定义C[i][j]如下： { j i j y i 且x ,i,j ]][j C[i j y i x j i j i C j i C j i C 00001110,]},1][[],][1[max{]][[===>+--≠>--=或，且为了构造出LCS ，还需要使用一个二维数组b[m][n]，b[i][j]记录C[i][j]是通过哪个子问题的值求得的，以决定搜索的方向，欲求出所有的LCS ，定义数组b 如下：设1-对角线方向;2-向上;3-向左;4-向上或向左若X[i]=Y[j],b[i][j] = 1, 若C[i-1][j][i][j-1], 则b[i][j] = 3, 若C[i-1][j]=[i][j-1], 则b[i][j] = 4, 根据以上辅助数组C 和b 的定义，算法首先需要求出这两个数组， C[m][n]中记录的最长公共子序列的长度，b 中记录了查找子序列元素的搜索方向。利用C 和b 的信息，Find_All_LCS 可以采用回溯法求出所有的LCS 。基本思路如下：使用一个辅助数组记录每次调用Find_All_LCS 得到的LCS 中的元素，每次递归调用一次Find_All_LCS ，进入一个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0 ，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于数组C 中求出的最长公共子序列长度，若等于，则说明算法执行到此已经得到一个LCS ，按序输出；若不等于，此时根据数组b 中记录的搜索方向继续搜索，特别要说明的是，当b[i][j]=4时，即要向上或向左，需要对这两个方向分别调用Find_All_LCS ，保证沿着这两个方向上LCS 元素不被漏掉，都可以搜索到；若b[i][j]=1，即沿对角线方向搜索前进时，此时元素X[i]为LCS 中的元素，存放至辅助数组中去，同时将当前已经求得的LCS 长度增1，当递归调用Find_All_LCS 从b[i][j]=1处时，需要回溯一步，搜索其它路径上可能为LCS 中的元素。当所有的可能路径都已经搜索完，算法结束。对于某些情况会输出重复的LCS ，这是因为算法在沿不同路径搜索时可能会出现相同的LCS 序列。 2、时间复杂度分析由上述对Find_All_LCS 算法的分析可知，求出所有的LCS 实际上是根据搜索的方向信息遍历所有的路径找出满足条件的元素集合。因此，除求解辅助数组C 和b 所用的O(mn+m+n)的执行时间外，Find_All_LCS 的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的情况下，即m=n 并且b 中所有的值都指示沿着对角线方向搜索，时间复杂度为O(n). 相反，当X 和Y 序列不存在公共子序列时为算法的最坏情况，此时C 中所有值都等于0，数组b 中所有的值都指示要分别沿两个不同的方向（向左或向上）搜索，这种情况下每处理一次X[i],Y[j]时总是要沿两个方向分别调用Find_All_LCS ，遇到i=0或j=0时返回，直到搜索完所有的可能路径才结束，最坏情况下的搜索矩阵如下图所示：

最长公共子序列(LCS)问题

程序员编程艺术第十一章：最长公共子序列(LCS)问题 0、前言程序员编程艺术系列重新开始创作了（前十章，请参考程序员编程艺术第一~十章集锦与总结）。回顾之前的前十章，有些代码是值得商榷的，因当时的代码只顾阐述算法的原理或思想，所以，很多的与代码规范相关的问题都未能做到完美。日后，会着力修善之。搜遍网上，讲解这个LCS问题的文章不计其数，但大多给读者一种并不友好的感觉，稍感晦涩，且代码也不够清晰。本文力图避免此些情况。力保通俗，阐述详尽。同时，经典算法研究系列的第三章（三、dynamic programming）写的极其糟糕，所以，也算是对那文的一种弥补。有任何问题，欢迎不吝赐教。第一节、问题描述什么是最长公共子序列呢?好比一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。举个例子，如：有两条随机序列，如1 3 4 5 5 ，and 2 4 5 5 7 6，则它们的最长公共子序列便是：4 5 5。第二节、LCS问题的解决思路 ?穷举法解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X和Y的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列（Y亦如此，如为2^n），从而穷举搜索法需要指数时间（2^m * 2^n）。 ?动态规划算法事实上，最长公共子序列问题也有最优子结构性质。记: Xi=﹤x1，?，xi﹥即X序列的前i个字符(1≤i≤m)（前缀） Yj=﹤y1，?，yj﹥即Y序列的前j个字符(1≤j≤n)（前缀）假定Z=﹤z1，?，zk﹥∈LCS(X , Y)。