Longest common substring: Difference between revisions
Content added Content deleted
(→C#: Compressing.) |
(→C#: Tweaking comments.) |
||
Line 17: | Line 17: | ||
Console.ReadKey(true); |
Console.ReadKey(true); |
||
} |
} |
||
//This algorithm for finding the longest commmon substring uses dynamic programming. |
|||
public static string lcs(string a, string b) |
public static string lcs(string a, string b) |
||
{ |
{ |
||
Line 23: | Line 25: | ||
string output = ""; |
string output = ""; |
||
// |
//Compare each consecutive character in string a with each consecutive character in string b. |
||
for (int i = 0; i < a.Length; i++) |
for (int i = 0; i < a.Length; i++) |
||
{ |
{ |
||
//For each character in string b... |
|||
for (int j = 0; j < b.Length; j++) |
for (int j = 0; j < b.Length; j++) |
||
{ |
{ |
Revision as of 11:27, 18 February 2015
Longest common substring is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Write a program that prompts the user to enter two different strings, and then output their longest common substring.
C#
<lang csharp>using System; namespace LongestCommonSubstring {
class Program { static void Main(string[] args) { Console.Write("Enter word 1: "); string word1 = Console.ReadLine(); Console.Write("Enter word 2: "); string word2 = Console.ReadLine(); Console.WriteLine(lcs(word1, word2)); Console.ReadKey(true); }
//This algorithm for finding the longest commmon substring uses dynamic programming. public static string lcs(string a, string b) { var lengths = new int[a.Length, b.Length]; int greatestLength = 0; string output = "";
//Compare each consecutive character in string a with each consecutive character in string b. for (int i = 0; i < a.Length; i++) { for (int j = 0; j < b.Length; j++) { //Keep a running count of the number of consecutive characters in each that are the same. if (a[i] == b[j]) { if (i == 0 || j == 0) { lengths[i, j] = 1; } else { lengths[i, j] = lengths[i - 1, j - 1] + 1; }
//When you find the greatest count so far, note the substring of which it is. if (lengths[i, j] > greatestLength) { greatestLength = lengths[i, j]; output = a.Substring(i - greatestLength + 1, greatestLength); } } else { lengths[i, j] = 0; } } }
//Output the substring you've noted. return output; } }
}</lang>