资源描述：
《C#匹配最长子字符串(能避开空格)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、摘要随着信息化时代的到来，伴随着的是网络上大量的垃圾信息与屡禁不止，难辨真伪的抄袭现象，急需一种能够排除空格换行等干扰符号，求解最长公共子序列的一种高效算法，能够排查网上带空格回车的不良言语以及完成论文查重等事件。本人使用正则表达式巧妙地去除了字符串中的空格与换行符，使用C#语言完成了基于动态规划的最长公共子序列的求解，并使用两个程序对TXT文件和对DOC文件中字符串求解最长公共子序列。（ConsoleApplication3针对TXT文件，ConsoleApplication6针对DOC文件）目录1.实验设计及要求2.实验思路2.1刻画最长公共子序列的特征2.2一个递归解3.
2、实验内容及其步骤3.1去除字符串中的干扰符号（空格与换行符）3.2计算LCS的长度3.3构造LCS4.测试运行5.实验小结附录1.实验设计及要求使用某种语言先去除字符串中的空格与换行符，再完成基于动态规划的最长公共子序列的求解，并使用程序对文本文档中字符串求解最长公共子序列。2.实验思路2.1刻画最长公共子序列的特征子问题的自然分类对应两个输入序列的“前缀”对。前缀的严谨定义如下：给定一个序列X=，对i=0,1,...,m,定义X的第i前缀为Xi=。例如若X=,则X4=,X0
3、为空串。定理15.1（LCS的最优子结构）令X=和Y=为两个序列，Z=为X和Y的任意LCS。1.如果xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的一个LCS。2.如果xm≠yn，则zk≠xm意味着Z是Xm-1和Y的一个LCS。3.如果xm≠yn，则zk≠yn意味着Z是X和Yn-1的一个LCS。2.2一个递归解求X=和Y=的一个LCS时，我们需要求解一个或两个子问题。如果xm=yn,我们应该求解Xm-1和Yn-1的一个LCS。
4、将xm=yn追加到这个LCS的末尾，就得到X和Y的一个LCS。如果xm≠yn我们必须求解两个子问题：求Xm-1和Y的一个LCS与X和Yn-1的一个LCS。两个LCS较长者即为X和Y的一个LCS。由于这些情况覆盖了所有可能性，因此我们知道必然有一个子问题的最优解出现在X和Y的LCS中。我们可以很容易看出LCS问题的重叠子问题性质。为了求X和Y的一个LCS，我们可能需要求X和Yn-1的一个LCS。但是这几个自问题都包含求解Xm-1和Yn-1的LCS的子子子问题。很多其他子问题也都共享子子问题。与矩阵链乘法问题相似，设计LCS问题的递归算法首先要建立最优解的递归式。我们定义c[i,j
5、]表示Xi和Yi的LCS的长度。如果i=0或j=0，即一个序列长度为0，那么LCS的长度为0。根据LCS问题的最优子结构性质，可得如下公式：0若i=0或j=0c[i,j]=c[i-1,j-1]+1若i,j>0且xi=yimax(c[i-1,j],c[i,j-1])若i,j>0且xi≠yi观察到在递归公式中，我们通过限制条件限定了需要求解那些子问题。当xi=yi时，我们可以而且应该求解子问题：Xi-1和Yj-1的一个LCS。否则，应该求解两个子问题：Xi和Yj-1的一个LCS及Xi-1和Yj的一个LCS。3.实验内容及其步骤3.1去除字符串中的干扰符号（空格与换行符）将文件中字符
6、串导入程序，分别存入两个字符串中，使用正则表达式Regex.Matches(X,"[^]+")，将不包含空格与回车的字符串片段放入MatchCollection中，将片段拼接起来形成不含空格与回车的两个新字符串。源码如下：stringX=File.ReadAllText(@".1.txt");stringY=File.ReadAllText(@".2.txt");MatchCollectionv1=Regex.Matches(X,"[^]+");MatchCollectionv2=Regex.Matches(Y,"[^]+");StringBuilderx1=n
7、ewStringBuilder();StringBuilderx2=newStringBuilder();foreach(Matchm1inv1){x1.Append(m1.Value);}foreach(Matchm2inv2){x2.Append(m2.Value);}stringx=""+x1.ToString();stringy=""+x2.ToString();3.2计算LCS的长度根据公式0若i=0或j=0c[i,j]=c[i-1,j-1]+1若i,j>0且xi=yimax(c[
