C匹配最长子字符串(能避开空格).docx

摘要随着信息化时代的到来，伴随着的是网络上大量的垃圾信息与屡禁不止，难辨真伪的抄袭现象，急需一种能够排除空格换行等干扰符号，求解最长公共子序列的一种高效算法，能够排查网上带空格回车的不良言语以及完成论文查重等事件。本人使用正则表达式巧妙地去除了字符串中的空格与换行符，使用C#语言完成了基于动态规划的最长公共子序列的求解，并使用两个程序对TXT文件和对DOC文件中字符串求解最长公共子序列。（ConsoleApplication3针对TXT文件，ConsoleApplication6针对DOC文件）目录实验设计及要求实验思路2.1刻画最长公共子序列的特征2.2一个递归解3. 实验内容及其步骤3.1去除字符串中的干扰符号（空格与换行符）3.2计算LCS的长度3.3构造LCS4. 测试运行5. 实验小结附录实验设计及要求使用某种语言先去除字符串中的空格与换行符，再完成基于动态规划的最长公共子序列的求解，并使用程序对文本文档中字符串求解最长公共子序列。实验思路2.1刻画最长公共子序列的特征子问题的自然分类对应两个输入序列的“前缀”对。前缀的严谨定义如下：给定一个序列X=x1,x2,...,xm，对i=0,1,...,m,定义X的第i前缀为Xi=x1,x2,...,xi。例如若X=A,B,C,B,D,A,B,则X4=A,B,C,B,X0为空串。定理15.1（LCS的最优子结构） 令X=x1,x2,...,xm和Y=y1,y2,...,yn为两个序列，Z=z1,z2,...,zk为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=x1,x2,...,xm和Y=y1,y2,...,yn的一个LCS时，我们需要求解一个或两个子问题。如果xm=yn,我们应该求解Xm-1和Yn-1的一个LCS。将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]表示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,j0且xi=yi max(c[i-1,j],c[i,j-1]) 若i,j0且xi≠yi 观察到在递归公式中，我们通过限制条件限定了需要求解那些子问题。当xi=yi时，我们可以而且应该求解子问题：Xi-1和Yj-1的一个LCS。否则，应该求解两个子问题：Xi和Yj-1的一个LCS及Xi-1和Yj的一个LCS。3. 实验内容及其步骤3.1去除字符串中的干扰符号（空格与换行符）将文件中字符串导入程序，分别存入两个字符串中，使用正则表达式Regex.Matches(X, [^ \n]+)，将不包含空格与回车的字符串片段放入MatchCollection中，将片段拼接起来形成不含空格与回车的两个新字符串。源码如下：string X = File.ReadAllText(@.\1.txt); string Y = File.ReadAllText(@.\2.txt); MatchCollection v1 = Regex.Matches(X, [^ \n]+); MatchCollection v2 = Regex.Matches(Y, [^ \n]+); StringBuilder x1 = new StringBuilder(); StringBuilder x2 = new StringBuilder(); foreach (Match m1 in v1) { x1.Append(m1.Value); } foreach (Match m2 in v2) { x2.Append(m2.Value); } string x = +x1.ToString(); string y = +x2.ToString();3.2计算LCS的长度根据公式 0若i=0或j=0c[i