c# - 如何获得在集合数量中找到的最长匹配项，顺序很重要

Question

当项目的顺序很重要时，我需要找到一种方法来返回在集合/列表数量中找到的最长匹配项(值仅返回一次)。 该列表不是循环的。

匹配是所有列表中存在的值序列，并在所有列表中保持相同的元素顺序。

例如1:

    List<int> list1 = new List<int> { 1, 2, 3, 4, 7, 9 };
    List<int> list2 = new List<int> { 1, 2, 5, 6, 3, 4, 7, 9 };
    List<int> list3 = new List<int> { 1, 2, 3, 6, 8, 9 };
    List<int> list4 = new List<int> { 1, 2, 5, 6, 8, 9 };

结果 { 1, 2 }

例如2:

     List<int> list1 = new List<int> { 2, 3, 6, 8, 1, 18 };
     List<int> list2 = new List<int> { 2, 3, 4, 6, 8, 1, 18, 19, 17, 14 };
     List<int> list3 = new List<int> { 2, 5, 6, 8, 1, 18, 16, 13, 14 };
     List<int> list4 = new List<int> { 2, 6, 8, 1, 18, 19, 17, 14 };

结果 { 6, 8, 1, 18 }

不必在开头或结尾找到匹配项，可以在任何列表的任何部分。

我希望我对我的问题的解释足够好:)

谢谢!

Answer 1

您可以从成对的整数构建一个映射，以计算它们出现在相邻列表中的数量。

伪代码:

For each list L {
    For each adjacent pair (x, y) in L {
         Counts[x, y] += 1
    }
}

现在您可以遍历第一个列表(或最短列表)，并找到最长的运行，使得运行中的每个相邻对 (x, y) 具有 Counts[x, y] 显示该对出现在每个列表。

伪代码:

run = []
best_run = []
For x in L[0] {
    if len(run) is zero or Counts[run[len(run)-1], x] == number of lists {
        run = run + x
    } else {
        run = [x]
    }
    if run is longer than best_run {
        best_run = run
    }
}

假设问题中没有整数在同一个列表中出现两次，这是可行的。

该算法运行时间为 O(N)，其中 N 是所有列表长度的总和。