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

《C匹配最长子字符串(能避开空格)》由会员分享，可在线阅读，更多相关《C匹配最长子字符串(能避开空格)（14页珍藏版）》请在文档大全上搜索。

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为空串。定理15.1（LCS的最优子结构） 令X=和Y=为两个序列，Z=为X和Y的任意LCS。1.如果xm=yn，则zk=xm

3、=yn且Zk-1是Xm-1和Yn-1的一个LCS。2.如果xmyn，则zkxm意味着Z是Xm-1和Y的一个LCS。3.如果xmyn，则zkyn意味着Z是X和Yn-1的一个LCS。2.2一个递归解求X=和Y=的一个LCS时，我们需要求解一个或两个子问题。如果xm=yn,我们应该求解Xm-1和Yn-1的一个LCS。将xm=yn追加到这个LCS的末尾，就得到X和Y的一个LCS。如果xmyn我们必须求解两个子问题：求Xm-1和Y的一个LCS与X和Yn-1的一个LCS。两个LCS较长者即为X和Y的一个LCS。由于这些情况覆盖了所有可能性，因此我们知道必然有一个子问题的最优解出现在X和Y的LCS中。我们可

4、以很容易看出LCS问题的重叠子问题性质。为了求X和Y的一个LCS，我们可能需要求X和Yn-1的一个LCS。但是这几个自问题都包含求解Xm-1和Yn-1的LCS的子子子问题。很多其他子问题也都共享子子问题。与矩阵链乘法问题相似，设计LCS问题的递归算法首先要建立最优解的递归式。我们定义ci,j表示Xi和Yi的LCS的长度。如果i=0或j=0，即一个序列长度为0，那么LCS的长度为0。根据LCS问题的最优子结构性质，可得如下公式： 0 若i=0或j=0ci,j= ci-1,j-1+1 若i,j0且xi=yi max(ci-1,j,ci,j-1) 若i,j0且xiyi 观察到在递归公式中，我们通过限

5、制条件限定了需要求解那些子问题。当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.ReadA

6、llText(.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();

7、 string y = +x2.ToString();3.2计算LCS的长度根据公式 0 若i=0或j=0ci,j= ci-1,j-1+1 若i,j0且xi=yi max(ci-1,j,ci,j-1) 若i,j0且xiyi我们可以很容易地写出一个指数时间的递归算法来计算两个序列的LCS的长度。但是，由于LCS问题只有(mn)个不同的子问题，我们可以根据动态规划方法自底向上地计算。 过程LCS-LENTH接受两个序列X=和Y=为输入，它将ci,j的值保存在表c0.m,0.n中，并按行主次序（row-major order）计算表项（即首先由左至右计算c的第一行，然后计算第二行，以此类推）。过程还

8、维护一个表b1.m,1.n,帮助构造最优解。Bi,j指向的表项对应计算ci,j时所选择的子问题最优解。过程返回表b和表c,cm,n保存了X和Y的LCS的长度。static void Main(string args) 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 StringBu

9、ilder(); 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(); int, c = new intx.Length,y.Length; string, b = new stringx.Length,y.Length ; string son=; int m = x.Lengt

10、h-1; int n = y.Length-1; for (int i = 1; i = m; i+) ci, 0 = 0; for (int j = 0; j = n; j+) c0, j = 0; for (int i = 1; i = m; i+) for (int j = 1; j = ci, j - 1) ci, j = ci - 1, j; bi, j = u; else ci, j = ci, j - 1; bi, j = l; print(b, x, m, n); Console.ReadKey(); 3.3构造LCS我们可以用LCS-LENGTH返回的表b快速构造X=和Y的L

11、CS，只需简单地从bm,n开始，并按箭头方向追踪下去即可。当在表项bi,j中遇到一个“LU”时，意味着xi=yi是LCS的一个元素。按照这种方法，我们可以按逆序依次构造出LCS的所有元素。下面的递归过程会按照正确的顺序打印出X和Y的一个LCS。对它的起始调用为print（b,X,X.length,Y.length）public static void print(string, b,string x,int i,int j) if (i = 0 | j = 0) return; if (bi, j = lu) print(b, x, i - 1, j - 1); Console.Write(x