Tìm một chuỗi trong chuỗi dài hơn

Question

Tôi cần tìm chuỗi trong chuỗi lớn khác, ví dụ: {1,3,2,3} có trong {1,3,2,3,4,3} và {5,1,3,2,3}. Có cách nào để thực hiện nhanh chóng với IEnumerable hoặc bằng cách nào khác không?

Answer 1

Bạn có thể thử một cái gì đó như thế này để giúp bạn bắt đầu. Một khi bạn đã chuyển đổi danh sách này thành một chuỗi, bạn có thể tìm thấy những chuỗi bằng cách sử dụng chuỗi con:

if (String.Join(",", numericList.ConvertAll<string>(x => x.ToString()).ToArray()) 
{ 
    //get sequence 
} 

Answer 2

Phương pháp này sẽ tìm thấy một dãy con trong một chuỗi phụ huynh, của bất kỳ loại có thể được so sánh qua Equals():

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target) 
{ 
    bool foundOneMatch = false; 
    using (IEnumerator<T> parentEnum = parent.GetEnumerator()) 
    { 
     using (IEnumerator<T> targetEnum = target.GetEnumerator()) 
     { 
      // Get the first target instance; empty sequences are trivially contained 
      if (!targetEnum.MoveNext()) 
       return true; 

      while (parentEnum.MoveNext()) 
      { 
       if (targetEnum.Current.Equals(parentEnum.Current)) 
       { 
        // Match, so move the target enum forward 
        foundOneMatch = true; 
        if (!targetEnum.MoveNext()) 
        { 
         // We went through the entire target, so we have a match 
         return true; 
        } 
       } 
       else if (foundOneMatch) 
       { 
        return false; 
       } 
      } 

      return false; 
     } 
    } 
} 

Bạn có thể sử dụng nó như thế này:

bool match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 2}); // match == true 
match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 3}); // match == false 

Lưu ý rằng nó giả định trình tự mục tiêu không có người null yếu tố.

Cập nhật: Cảm ơn upvotes, tất cả mọi người, nhưng có thực sự là một lỗi trong đoạn code trên! Nếu tìm thấy một phần khớp, nhưng sau đó không biến thành một kết hợp đầy đủ, quá trình này là đã kết thúc, thay vì đặt lại (rõ ràng là không được khắc phục khi áp dụng cho một cái gì đó như {1, 2, 1, 2, 3}.ContainsSubsequence({1, 2, 3})).

Đoạn mã trên hoạt động thực sự tốt cho định nghĩa phổ biến hơn về sau (nghĩa là không cần tiếp giáp) nhưng để xử lý việc cài đặt lại (hầu hết các số IEnumerators không hỗ trợ), thì chuỗi đích cần được liệt kê phía trước. Điều đó dẫn đến mã sau:

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target) 
{ 
    bool foundOneMatch = false; 
    var enumeratedTarget = target.ToList(); 
    int enumPos = 0; 

    using (IEnumerator<T> parentEnum = parent.GetEnumerator()) 
    { 
     while (parentEnum.MoveNext()) 
     { 
      if (enumeratedTarget[enumPos].Equals(parentEnum.Current)) 
      { 
       // Match, so move the target enum forward 
       foundOneMatch = true; 
       if (enumPos == enumeratedTarget.Count - 1) 
       { 
        // We went through the entire target, so we have a match 
        return true; 
       } 

       enumPos++; 
      } 
      else if (foundOneMatch) 
      { 
       foundOneMatch = false; 
       enumPos = 0; 

       if (enumeratedTarget[enumPos].Equals(parentEnum.Current)) 
       { 
        foundOneMatch = true; 
        enumPos++; 
       } 
      } 
     } 

     return false; 
    } 
} 

Mã này không có lỗi, nhưng sẽ không hoạt động tốt cho các chuỗi lớn (hoặc vô hạn).

Answer 3

Tương tự như @ dlev của nhưng điều này cũng xử lý {1,1,1,2}.ContainsSubsequence({1,1,2})

public static bool ContainsSubsequence<T>(this IEnumerable<T> parent, IEnumerable<T> target) 
{ 
    var pattern = target.ToArray(); 
    var source = new LinkedList<T>(); 
    foreach (var element in parent) 
    { 
     source.AddLast(element); 
     if(source.Count == pattern.Length) 
     { 
      if(source.SequenceEqual(pattern)) 
       return true; 
      source.RemoveFirst(); 
     } 
    } 
    return false; 
} 

Answer 4

này làm việc cho tôi

var a1 = new List<int> { 1, 2, 3, 4, 5 }; 
var a2 = new List<int> { 2, 3, 4 }; 

int index = -1; 
bool res = a2.All(
    x => index != -1 ? (++index == a1.IndexOf(x)) : ((index = a1.IndexOf(x)) != -1) 
); 

Answer 5

Hàm này kiểm tra liệu Danh sách parent chứa Danh sách target sử dụng một số LINQ:

public static bool ContainsSequence<T>(this List<T> parent, List<T> target) 
    { 
     for (int fromElement = parent.IndexOf(target.First()); 
      (fromElement != -1) && (fromElement <= parent.Count - target.Count); 
      fromElement = parent.FindIndex(fromElement + 1, p => p.Equals(target.First()))) 
     { 
      var comparedSequence = parent.Skip(fromElement).Take(target.Count); 
      if (comparedSequence.SequenceEqual(target)) return true; 
     } 
     return false; 
    }  

Answer 6

Nếu bạn đang xử lý đơn giản serializable loại, bạn có thể làm điều đó khá dễ dàng nếu bạn chuyển đổi các mảng chuỗi:

public static bool ContainsList<T>(this List<T> containingList, List<T> containedList) 
{ 
    string strContaining = "," + string.Join(",", containingList) + ","; 
    string strContained = "," + string.Join(",", containedList) + ","; 
    return strContaining.Contains(strContained); 
} 

Lưu ý đó là một phương pháp khuyến nông, vì vậy bạn sẽ có thể gọi nó là thích:

if (bigList.ContainsList(smallList)) 
{ 
    ... 
}