-
Notifications
You must be signed in to change notification settings - Fork 53
/
Copy pathLongestCommonSubstring.cs
58 lines (52 loc) · 2.04 KB
/
LongestCommonSubstring.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace FuzzyString
{
public static partial class ComparisonMetrics
{
public static string LongestCommonSubstring(this string source, string target)
{
if (String.IsNullOrEmpty(source) || String.IsNullOrEmpty(target)) { return null; }
int[,] L = new int[source.Length, target.Length];
int maximumLength = 0;
int lastSubsBegin = 0;
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < source.Length; i++)
{
for (int j = 0; j < target.Length; j++)
{
if (source[i] != target[j])
{
L[i, j] = 0;
}
else
{
if ((i == 0) || (j == 0))
L[i, j] = 1;
else
L[i, j] = 1 + L[i - 1, j - 1];
if (L[i, j] > maximumLength)
{
maximumLength = L[i, j];
int thisSubsBegin = i - L[i, j] + 1;
if (lastSubsBegin == thisSubsBegin)
{//if the current LCS is the same as the last time this block ran
stringBuilder.Append(source[i]);
}
else //this block resets the string builder if a different LCS is found
{
lastSubsBegin = thisSubsBegin;
stringBuilder.Length = 0; //clear it
stringBuilder.Append(source.Substring(lastSubsBegin, (i + 1) - lastSubsBegin));
}
}
}
}
}
return stringBuilder.ToString();
}
}
}