1

我有一个要在列表 B 中找到的通用点 NET 列表 A - 如何在列表 B 中找到列表 A？我需要列表 A 在列表 B 中的起始位置的索引。

4

4 回答 4

2

这是此答案的通用实现，它允许任何IList并且可以传入可选的IEqualityComparer. 这不是最快的搜索方式，但它是一个很好的起点，可以做一个更高级的答案。

static class GenericSearcher
{

    static readonly int[] Empty = new int[0];

    public static int[] Locate<T>(this IList<T> self, IList<T> candidate)
    {
        return Locate(self, candidate, EqualityComparer<T>.Default);
    }

    public static int[] Locate<T>(this IList<T> self, IList<T> candidate, IEqualityComparer<T> comparer)
    {
        if (IsEmptyLocate(self, candidate))
            return Empty;

        var list = new List<int>();

        for (int i = 0; i < self.Count; i++)
        {
            if (!IsMatch(self, i, candidate, comparer))
                continue;

            list.Add(i);
        }

        return list.Count == 0 ? Empty : list.ToArray();
    }

    static bool IsMatch<T>(IList<T> array, int position, IList<T> candidate, IEqualityComparer<T> comparer)
    {
        if (candidate.Count > (array.Count - position))
            return false;

        for (int i = 0; i < candidate.Count; i++)
            if (comparer.Equals(array[position + i],candidate[i]) == false)
                return false;

        return true;
    }

    static bool IsEmptyLocate<T>(ICollection<T> array, ICollection<T> candidate)
    {
        return array == null
            || candidate == null
            || array.Count == 0
            || candidate.Count == 0
            || candidate.Count > array.Count;
    }

}

用VB 代码更新（感谢ajakblackgoat）：

Module GenericSearcher

    Private ReadOnly Empty As Integer() = New Integer(-1) {}

    <System.Runtime.CompilerServices.Extension> _
    Public Function Locate(Of T)(self As IList(Of T), candidate As IList(Of T)) As Integer()
        Return Locate(self, candidate, EqualityComparer(Of T).[Default])
    End Function

    <System.Runtime.CompilerServices.Extension> _
    Public Function Locate(Of T)(self As IList(Of T), candidate As IList(Of T), comparer As IEqualityComparer(Of T)) As Integer()
        If IsEmptyLocate(self, candidate) Then
            Return Empty
        End If

        Dim list = New List(Of Integer)()

        For i As Integer = 0 To self.Count - 1
            If Not IsMatch(self, i, candidate, comparer) Then
                Continue For
            End If

            list.Add(i)
        Next

        Return If(list.Count = 0, Empty, list.ToArray())
    End Function

    Private Function IsMatch(Of T)(array As IList(Of T), position As Integer, candidate As IList(Of T), comparer As IEqualityComparer(Of T)) As Boolean
        If candidate.Count > (array.Count - position) Then
            Return False
        End If

        For i As Integer = 0 To candidate.Count - 1
            If Not comparer.Equals(array(position + i), candidate(i)) Then
                Return False
            End If
        Next

        Return True
    End Function

    Private Function IsEmptyLocate(Of T)(array As ICollection(Of T), candidate As ICollection(Of T)) As Boolean
        Return array Is Nothing OrElse candidate Is Nothing OrElse array.Count = 0 OrElse candidate.Count = 0 OrElse candidate.Count > array.Count
    End Function

End Module
于 2013-06-18T01:55:07.777 回答
2

有一种非常幼稚的方法是O(|A| * |B|)。基本上，这是天真的子字符串搜索算法1：

for(int i = 0; i < B.Count - A.Count; i++) {
     bool matchPossible = true;
     for(int j = 0; matchPossible && j < A.Count; j++) {
         if (!B[i + j].Equals(A[j])) { // should check for B[i + j] == null
              matchPossible = false;
              break;
         }
     }
     if(matchPossible) {
         return i;
     }
 }     
 return -1;

我遗漏了一些你应该做的明显错误检查，这样你就可以专注于方法。我评论了其中一项明显的检查。B这将为您提供A 可以找到的索引。

我会坚持这一点，除非基准测试表明这种方法正在拖累你。如果是这样，你需要看看像 Knuth-Morris-Pratt 这样更复杂的东西。

ListA和 ListB都声明为List<string>; 我在想可能有办法用 LINQ 做到这一点？A在列表中查找列表B？

当然。

for(int i = 0; i < B.Count - A.Count; i++) {
    if(B.SequenceEqual(A.Skip(i).Take(B.Count))) {
        return i;
    }
}
return -1;

请注意，这与我上面给出的算法基本相同，只是表达得更清楚一点。但是，这种方法有一个缺点。我不知道它是否Enumerable.Skip足够聪明，可以在索引器可用时使用它。如果不使用索引器，此版本的性能可能低于原始版本。这就是我在最初的方法中没有使用它的原因。

此外，您必须翻译成 VB.NET，抱歉；我手边没有编译器，而且我说流利的 C#（所以不需要编译器来检查我的语法），但不是 VB。

1：出于某种原因，我突然回想起这种方法包含在 K&R 的小 C 书中？任何人都可以验证；我不知道我的副本现在在哪里？2

2：找到了。是的，第 4.1 节。功能是strindex。

于 2013-06-18T01:43:49.310 回答
1

试试这个接收ListA和的函数ListB：

Dim index As Integer = listB.IndexOf(listA(0))
Dim iCont As Integer
Dim bMatch As Boolean

While index >= 0
    bMatch = True
    iCont = 1

    'Check if lists match on all the items in list A
    While bMatch
        index += 1
        bMatch = (index < listB.Count) AndAlso (listA(iCont) = listB(index))

        iCont += 1
        If iCont >= ListA.Count Then Exit While
    End While         

    If bMatch Then Exit While
    index = listB.IndexOf(listA(0), index)
End While

return bMatch
于 2013-06-18T07:24:33.627 回答
0

这是一个相当简单的方法。它应该适用于任何具有相等比较器的类型。我用字符串和整数列表测试了它。此函数仅迭代 ListB 的第一个元素。因此，它只会步进与 ListA 中与 ListB 中的第一个元素相等的元素到开始相等序列的元素的次数一样多。

Private Function FindList(Of T)(ListA As IList(Of T), ListB As List(Of T)) As Integer
    Dim FoundIndex As Integer = ListA.IndexOf(ListB(0))
    Dim FoundlList As Boolean = False
    While FoundIndex <> -1
        If ListA.Skip(FoundIndex).Take(ListB.Count).SequenceEqual(ListB) Then
            Return FoundIndex
        End If
        FoundIndex = FindIndex(ListA, FoundIndex, ListB(0))
    End While
    Return FoundIndex
End Function
Private Function FindIndex(Of T)(List As IList(Of T), Start As Integer, FindItem As T) As Integer
    Dim TempList = List.Skip(Start + 1).ToList
    Return TempList.IndexOf(FindItem) + (List.Count - TempList.Count)
End Function
于 2013-06-19T08:42:27.333 回答