我已经编写了这些函数(它们可以工作)来查找两个字符串的最长公共子序列。
def lcs_grid(xs, ys):
grid = defaultdict(lambda: defaultdict(lambda: (0,"")))
for i,x in enumerate(xs):
for j,y in enumerate(ys):
if x == y:
grid[i][j] = (grid[i-1][j-1][0]+1,'\\')
else:
我的alg&dat书介绍了这个最长公共子序列长度的算法:
public static int LCSLength (int[] X, int[] Y, int i, int j) {
if(i==0 || j ==0) {
return 0;
}
else if (X[i-1]==Y[j-1]) {
return 1+LCSLength(X,Y,i-1,j-1);
}
else if(LCSLength(X,Y,i-1,j)>LCSLength(X,Y,i,j-1)){
return
我在一个字符串问题中求解最长的回文,在这里我们正在寻找形成回文的最长子字符串。我上面的代码是:
private static int palindrome(char[] ch, int i, int j) {
// TODO Auto-generated method stub
if (i == j)
return 1;
// Base Case 2: If there are only 2 characters and both are same
if (ch[i] == ch[j] && i + 1 == j)
我已经为LCS编写了以下代码。它在许多情况下都有效,但在下面的情况下会中断。我不知道我的代码在哪里崩溃了。请帮帮忙。代码在C#中
namespace LongestCommonSubsequenceBF
{
class Program
{
static void Main(string[] args)
{
string B = "AAACCGTGAGTTATTCGTTCTAGAA";
string A = "CACCCCTAAGGTACCTTTGGTTC";
//find LCS in A,B s
嘿,伙计们,我在algoExpert平台上研究这个问题,但是我很难理解和currentLongest到底在做什么。
def longestPalindromicSubstring(string):
currentLongest = [0, 1]
for i in range(1, len(string)):
odd = getLongestPalindromeFrom(string, i - 1, i + 1)
even = getLongestPalidromeFrom(string, i - 1, i)
longest = max(odd, even, ke
下面的代码给出了最长的回文子序列长度。如何修改代码以获得最长的回文子字符串长度?
public static int lp(String str, int i, int j, int ans) {
if (i == str.length() || j <= 0)
return ans;
if (i > j)
return ans;
if (i == j)
return ans + 1;
if (str.charAt(i) == str.charAt(j)) {
int a
我必须建立一个函数,打印DNA片段中最长的回文子串。我已经写了一个函数来检查DNA片段是否是回文本身。请参见下面的函数。
def make_complement_strand(DNA):
complement=[]
rules_for_complement={"A":"T","T":"A","C":"G","G":"C"}
for letter in DNA:
complement.append(rules_for_comple
我已经写过LCS的部分了。
我想知道如果我给N(N>3),这意味着有多少组输入。
就像这样:
输入
4 ab abc abcd abc ab
输出
3.
只需找到最长的那些lcs(3序列的一部分)
ab abc abcd->ab->2
abc abc->abc>3
3>2
我的想法是,每一个集合都使用3个序列的方式,然后找到最大的一个。
但我不知道怎么做或者其他更好的方法?
这是我代码的一部分:
#define EQUAL(x,y,z) ((x)==(y)&&(y)==(z))
int main(){
int set;
int longe
嗨,这是我在c#中为2个字符串编写的最长公共子序列的代码。我需要回溯方面的帮助。我需要找出子序列: GTCGT
String str1 = "GTCGTTCG";
String str2 = "ACCGGTCGAGTG";
int[,] l = new int[str1.Length, str2.Length]; // String 1 length and string 2 length storing it in a 2-dimensional array
int lcs = -1;
string substr = string.Empty;
i
是否有(容易)的可能性来识别两个字符串共享的公共模式?这里有一个小例子来说明我的意思:
我有两个变量包含一个字符串。两者都包括相同的模式("ABC")和一些“噪音”。
a <- "xxxxxxxxxxxABCxxxxxxxxxxxx"
b <- "yyyyyyyyyyyyyyyyyyyyyyyABC"
假设我不知道常见的模式,我想让R知道这两个字符串都包含"ABC“。我该怎么做?
*编辑
第一个例子可能有点过于简单化。下面是我真实数据中的一个例子。
a <- "DUISBURG-HAMBORNS"
b &
LCS代码的递归版本如下(m,n分别是字符串X和Y的长度)
int lcs( char[] X, char[] Y, int m, int n ) {
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
我注意到,这个algo从末尾删除字符串的字符,并
我知道一般的LCS问题和算法。
就像这样:
LCS(Xi, Yj) = [0 (i = 0 or j = 0)
or LCS(Xi-1, Yj-1) + 1 (xi = yj)
or max(LCS(Xi, Yj-1), LCS(Xi-1, Yj)) (xi != yj)]
但是如果我们加上一个缺口条件呢?
例如:
String A is cttauaucagu
String B is cautauatcgu
if no gap condition
lcs = cauauagu
if gap = 1 (lcs gap is under 1)
lc
我为这个问题创建了一个递归的解决方案,但最大的错误是它不认识到一个包含在两个相同字符之间的其他字符的小回文并不一定是回文
public static int palindrome(String str)
{
str = str.toLowerCase();
if (str.length() == 0)
return 0;
if (str.length() == 1)
return 1;
if (str.charAt(0) == str.charAt(str.length() - 1))
{
int pal =