How to resolve the algorithm Longest common substring step by step in the C# programming language
How to resolve the algorithm Longest common substring step by step in the C# programming language
Table of Contents
Problem Statement
Write a function that returns the longest common substring of two strings. Use it within a program that demonstrates sample output from the function, which will consist of the longest common substring between "thisisatest" and "testing123testing". Note that substrings are consecutive characters within a string. This distinguishes them from subsequences, which is any sequence of characters within a string, even if there are extraneous characters in between them. Hence, the longest common subsequence between "thisisatest" and "testing123testing" is "tsitest", whereas the longest common substring is just "test".
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Longest common substring step by step in the C# programming language
The first code is a C# program that finds the Longest Common Substring (LCS) of two strings using dynamic programming. The LCS of two strings is the longest substring that is common to both strings.
The program uses a matrix to store the lengths of the LCSs of the substrings of the two input strings. The matrix is initialized to 0, indicating that there is no common substring between any of the substrings of the two input strings.
The program then iterates over the two input strings, and for each pair of characters, it checks if the characters are equal. If the characters are equal, then the program increments the corresponding entry in the matrix by 1. Otherwise, the program sets the corresponding entry in the matrix to 0.
After the program has iterated over the two input strings, the matrix contains the lengths of the LCSs of all of the substrings of the two input strings. The program then finds the maximum value in the matrix, and returns the substring corresponding to that value.
The second code is a C# program that finds the LCS of two strings using a brute-force approach. The program iterates over all of the substrings of the first input string, and checks if each substring is a substring of the second input string. If a substring is a substring of the second input string, then the program returns that substring.
The third code is a C# program that finds the LCS of two strings using a recursive approach. The program takes two strings as input, and returns the LCS of the two strings. If either of the input strings is empty, then the program returns an empty string. Otherwise, the program checks if the last character of the two strings is equal. If the last character of the two strings is equal, then the program returns the last character of the two strings, followed by the LCS of the rest of the two strings. Otherwise, the program returns the LCS of the first string, or the LCS of the second string.
The time complexity of the first code is O(mn), where m and n are the lengths of the two input strings. The time complexity of the second code is O(mn^2), where m and n are the lengths of the two input strings. The time complexity of the third code is O(2^n), where n is the length of the shorter of the two input strings.
Source code in the csharp programming language
using System;
namespace LongestCommonSubstring
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(lcs("thisisatest", "testing123testing"));
Console.ReadKey(true);
}
public static string lcs(string a, string b)
{
var lengths = new int[a.Length, b.Length];
int greatestLength = 0;
string output = "";
for (int i = 0; i < a.Length; i++)
{
for (int j = 0; j < b.Length; j++)
{
if (a[i] == b[j])
{
lengths[i, j] = i == 0 || j == 0 ? 1 : lengths[i - 1, j - 1] + 1;
if (lengths[i, j] > greatestLength)
{
greatestLength = lengths[i, j];
output = a.Substring(i - greatestLength + 1, greatestLength);
}
}
else
{
lengths[i, j] = 0;
}
}
}
return output;
}
}
}
//C# program tests the LCSUBSTR (Longest Common Substring) subroutine.
using System;
namespace LongestCommonSubstring
{
class Program
{
static void Main(string[] args)
{
string a = args.Length >= 1 ? args[0] : ""; /*get two arguments (strings). */
string b = args.Length == 2 ? args[1] : "";
if (a == "") a = "thisisatest"; /*use this string for a default. */
if (b == "") b = "testing123testing"; /* " " " " " " */
Console.WriteLine("string A = {0}", a); /*echo string A to screen. */
Console.WriteLine("string B = {0}", b); /*echo string B to screen. */
Console.WriteLine("LCsubstr = {0}", LCsubstr(a, b)); /*tell Longest Common Substring. */
Console.ReadKey(true);
} /*stick a fork in it, we're done.*/
/*─────────────────────────────────LCSUBSTR subroutine─────────────────────────────────*/
public static string LCsubstr(string x, string y) /*Longest Common Substring. */
{
string output = "";
int lenx = x.Length; /*shortcut for using the X length*/
for (int j = 0; j < lenx; j++) /*step through start points in X.*/
{
for (int k = lenx - j; k > -1; k--) /*step through string lengths. */
{
string common = x.Substring(j, k); /*extract a common substring. */
if (y.IndexOf(common) > -1 && common.Length > output.Length) output = common; /*longest?*/
} /*k*/
} /*j*/
return output; /*$ is "" if no common string. */
}
}
}
//C# program tests the LCS (Longest Common Substring) subroutine.
using System;
namespace LongestCommonSubstring
{
class Program
{
static void Main(string[] args)
{
string a = args.Length >= 1 ? args[0] : ""; /*get two arguments (strings). */
string b = args.Length == 2 ? args[1] : "";
if (a == "") a = "thisisatest"; /*use this string for a default. */
if (b == "") b = "testing123testing"; /* " " " " " " */
Console.WriteLine("string A = {0}", a); /*echo string A to screen. */
Console.WriteLine("string B = {0}", b); /*echo string B to screen. */
Console.WriteLine("LCS = {0}", lcs(a, b)); /*tell Longest Common Substring. */
Console.ReadKey(true);
} /*stick a fork in it, we're done.*/
/*─────────────────────────────────LCS subroutine─────────────────────────────────*/
private static string lcs(string a, string b)
{
if(b.Length<a.Length){ string t=a; a=b; b=t; }
for (int n = a.Length; n > 0; n--)
{
for (int m = a.Length-n; m <= a.Length-n; m++)
{
string s=a.Substring(m,n);
if(b.Contains(s)) return(s);
}
}
return "";
}
}
You may also check:How to resolve the algorithm Leonardo numbers step by step in the Modula-2 programming language
You may also check:How to resolve the algorithm Zeckendorf number representation step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Merge and aggregate datasets step by step in the Java programming language
You may also check:How to resolve the algorithm Case-sensitivity of identifiers step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm Runge-Kutta method step by step in the Ring programming language