therearetwouws
BAN USERC#
Cost: O(m + n)
private static List<int> lcs(int[] array1, int[] array2)
{
List<int> r1 = lcsInternal(array1, array2);
List<int> r2 = lcsInternal(array2, array1);
List<int> result;
// Get the longest
if (r1.Count >= r2.Count) { result = r1; }
else { result = r2; }
return result;
}
private static List<int> lcsInternal(int[] array1, int[] array2)
{
int l1 = array1.Length;
int l2 = array2.Length;
List<int> resultList = new List<int>();
// Initially start with 0
int startj = 0;
bool done = false;
for (int i = 0; i < l1 && !done; i++)
{
int v1 = array1[i];
for (int j = startj; j < l2; j++)
{
int v2 = array2[j];
// Not the same value, go to the next j
if (v1 != v2) { continue; }
// v1 == v2
// Store the result
resultList.Add(v1);
// Store the current j + 1 because it'll start there on
// the next iteration
startj = j + 1;
if (startj >= l2)
{
done = true;
}
// Stop the current j, and continue with i
break;
}
}
return resultList;
}
- therearetwouws May 19, 2019