我如何找到兩個大字符串之間的lcs長度

我已經在C#中編寫了下面的代碼，用於獲取兩個使用的文本中最長的公共子序列的長度，但它不適用於大字符串。你可以幫我嗎。我很困惑。我如何找到兩個大字符串之間的lcs長度

public Form1() 
{ 
    InitializeComponent(); 
} 

public int lcs(char[] s1, char[] s2, int s1size, int s2size) 
{ 
    if (s1size == 0 || s2size == 0) 
    { 
     return 0; 
    } 
    else 
    { 
     if (s1[s1size - 1] == s2[s2size - 1]) 
     { 
      return (lcs(s1, s2, s1size - 1, s2size - 1) + 1); 
     } 
     else 
     { 
      int x = lcs(s1, s2, s1size, s2size - 1); 
      int y = lcs(s1, s2, s1size - 1, s2size); 
      if (x > y) 
      { 
       return x; 
      } 
      else 
       return y; 
     } 
    } 
} 

private void button1_Click(object sender, EventArgs e) 
{ 
    string st1 = textBox2.Text.Trim(' '); 
    string st2 = textBox3.Text.Trim(' '); 

    char[] a = st1.ToCharArray(); 
    char[] b = st2.ToCharArray(); 

    int s1 = a.Length; 
    int s2 = b.Length; 

    textBox1.Text = lcs(a, b, s1, s2).ToString(); 
}

來源

2014-02-15 ilia7

多大影響你？爲什麼'c'標籤？ –

一個正常的段落。 – ilia7

使用'遞歸函數'原因發生這個問題的朋友，是否有可能不使用遞歸函數？ – Hamidreza

這裏您使用的是遞歸方法。所以它會導致程序發生性能問題，正如你所提到的那樣。

而不是遞歸，使用動態編程的方法。

這裏是C＃代碼。

public static void LCS(char[] str1, char[] str2) 
    { 
     int[,] l = new int[str1.Length, str2.Length]; 
     int lcs = -1; 
     string substr = string.Empty; 
     int end = -1; 

     for (int i = 0; i < str1.Length; i++) 
     { 
      for (int j = 0; j < str2.Length; j++) 
      { 
       if (str1[i] == str2[j]) 
       { 
        if (i == 0 || j == 0) 
        { 
         l[i, j] = 1; 
        } 
        else 
         l[i, j] = l[i - 1, j - 1] + 1; 
        if (l[i, j] > lcs) 
        { 
         lcs = l[i, j]; 
         end = i; 
        } 

       } 
       else 
        l[i, j] = 0; 
      } 
     } 

     for (int i = end - lcs + 1; i <= end; i++) 
     { 
      substr += str1[i]; 
     } 

     Console.WriteLine("Longest Common SubString Length = {0}, Longest Common Substring = {1}", lcs, substr); 
    }

來源

2014-02-15 12:42:43

這個問題被標記爲'C＃'。你應該提供'C＃'代碼。 – ajay

這是C＃代碼。 – artemisart

我想這是一個常見的算法 - 你有名字（或Cormen等人的章節或任何其他參考有價值的鏈接）？ – mbx

這裏是一個解決方案是如何找到在C＃中最長的公共子：

public static string GetLongestCommonSubstring(params string[] strings) 
{ 
    var commonSubstrings = new HashSet<string>(strings[0].GetSubstrings()); 
    foreach (string str in strings.Skip(1)) 
    { 
     commonSubstrings.IntersectWith(str.GetSubstrings()); 
     if (commonSubstrings.Count == 0) 
      return string.Empty; 
    } 

    return commonSubstrings.OrderByDescending(s => s.Length).DefaultIfEmpty(string.Empty).First(); 
} 

private static IEnumerable<string> GetSubstrings(this string str) 
{ 
    for (int c = 0; c < str.Length - 1; c++) 
    { 
     for (int cc = 1; c + cc <= str.Length; cc++) 
     { 
      yield return str.Substring(c, cc); 
     } 
    } 
}

我在這裏找到：http://www.snippetsource.net/Snippet/75/longest-common-substring

來源

2014-07-11 21:49:15

我如何找到兩個大字符串之間的lcs長度

回答

相關問題