41 lines
1.2 KiB
C#
41 lines
1.2 KiB
C#
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;
|
|
}
|
|
}
|
|
}
|