做网站如何推销,wordpress 去除版本号,仿站吧,网站进入之前动态效果1 最大公共子序列
最长的常见子序列问题是寻找两个给定字符串中存在的最长序列。
最大公共子序列算法#xff0c;常用于犯罪鉴定、亲子鉴定等等的 DNA 比对。
1.1 子序列
让我们考虑一个序列Ss1#xff0c;s2#xff0c;s3#xff0c;s4#xff0c;…#xff0c;… 1 最大公共子序列
最长的常见子序列问题是寻找两个给定字符串中存在的最长序列。
最大公共子序列算法常用于犯罪鉴定、亲子鉴定等等的 DNA 比对。
1.1 子序列
让我们考虑一个序列Ss1s2s3s4…sn。
一个序列Zz1z2z3z4…zm在S上被称为S的子序列当且仅当它可以从某些元素的S删除中派生出来时。
1.2 公共子序列
假设X和Y是有限元素集上的两个序列。如果Z是X和Y的子序列我们可以说Z是X和Y的公共子序列。
1.3 最长公共子序列
如果给定一组序列则最长公共子序列问题是找到所有序列中具有最大长度的公共子序列。
最长的常见子序列问题是一个经典的计算机科学问题是diff实用程序等数据比较程序的基础在生物信息学中有应用。它还被SVN和Git等版本控制系统广泛用于协调对受版本控制的文件集合所做的多个更改。
2 递归算法源程序
using System; using System.Text; using System.Collections; using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm { public static partial class StringSearch { /// summary /// 两个字符串的最大公共子字符串 /// /summary /// param nameX/param /// param nameY/param /// param namem/param /// param namen/param /// returns/returns public static int LCS_Solve(string X, string Y, int m, int n) { if (m 0 || n 0) { return 0; } if (X[m - 1] Y[n - 1]) { return 1 LCS_Solve(X, Y, m - 1, n - 1); } else { return Math.Max(LCS_Solve(X, Y, m, n - 1), LCS_Solve(X, Y, m - 1, n)); } } } }
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class StringSearch{/// summary/// 两个字符串的最大公共子字符串/// /summary/// param nameX/param/// param nameY/param/// param namem/param/// param namen/param/// returns/returnspublic static int LCS_Solve(string X, string Y, int m, int n){if (m 0 || n 0){return 0;}if (X[m - 1] Y[n - 1]){return 1 LCS_Solve(X, Y, m - 1, n - 1);}else{return Math.Max(LCS_Solve(X, Y, m, n - 1), LCS_Solve(X, Y, m - 1, n));}}}
}
3 非递归算法源程序 using System; using System.Text; using System.Collections; using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm { public static partial class StringSearch { /// summary /// 计算两个字符串的最大公共子字符串 /// /summary /// param nameX/param /// param nameY/param /// returns/returns public static int LCS_Solve(string X, string Y) { int m X.Length; int n Y.Length; int[,] LengthArray new int[m 1, n 1]; for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0 || j 0) { LengthArray[i, j] 0; } else if (X[i - 1] Y[j - 1]) { LengthArray[i, j] LengthArray[i - 1, j - 1] 1; } else { LengthArray[i, j] Math.Max(LengthArray[i - 1, j], LengthArray[i, j - 1]); } } } return LengthArray[m, n]; } } }
——————————————————————————
POWER BY TRUFFER.CN 50018.COM
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class StringSearch{/// summary/// 计算两个字符串的最大公共子字符串/// /summary/// param nameX/param/// param nameY/param/// returns/returnspublic static int LCS_Solve(string X, string Y){int m X.Length;int n Y.Length;int[,] LengthArray new int[m 1, n 1];for (int i 0; i m; i){for (int j 0; j n; j){if (i 0 || j 0){LengthArray[i, j] 0;}else if (X[i - 1] Y[j - 1]){LengthArray[i, j] LengthArray[i - 1, j - 1] 1;}else{LengthArray[i, j] Math.Max(LengthArray[i - 1, j], LengthArray[i, j - 1]);}}}return LengthArray[m, n];}}
}
