더 큰 시퀀스 내의 패턴을 모두 찾습니다.

Question

큰 시퀀스 내에서 패턴의 모든 항목을 찾는 효율적인 알고리즘을 원합니다. 다음 입력 주어진 예

:
패턴하십시오 similar question에 answer가 알고리즘을 구현 허용 따르면{4, 9}

: GAS
서열 ASDFGASDFGASDFADFASDFGA

예상 출력 원하는 작업을 달성하기 위해 그러나 하나의 comment은 알고리즘이 "큰 바이트 배열에서 느립니다"라고보고합니다.

주변을 읽은 후이 작업을 수행하는 가장 좋은 알고리즘은 Boyer-Moore String search algrorithm이며 C#의 구현은 CodeProject입니다.하지만 일반적인 enumerables에 구현하는 데 문제가 있습니다.

Boyer-Moore 알고리즘을 기반으로하는 기존의 솔루션이 .NET의 일반 시퀀스의 패턴을 모두 찾습니다.

주
내 예제에서 문자열을 사용하지만 내가는 IEnumerable을 구현하는 모든 데이터에 작동하는 대답을합니다. 다른 말로하면 그것은 문자열뿐만 아니라 어떤 유형에서도 작동해야합니다.

Answer 1

Boyer-Moore 알고리즘을 이해하기 위해 고생 한 후 더 큰 컬렉션을 단일 패턴으로 일치시키는이 코드를 조합했습니다.

나는 Boyer-Moore 알고리즘에 대해 테스트 할 수 없었지만, 전체 시퀀스가 ​​패턴을 반복 할 때 최악의 경우의 성능으로 O (nm)으로 매우 효율적으로 작동합니다.

여기가 제 구현입니다. 그것에 대한 당신의 견해를 알려주세요.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      Console.WriteLine("Enter the string you want to search within."); 
      string hayStack = Console.ReadLine(); 
      Console.WriteLine("Enter the string you want to search for."); 
      string needle = Console.ReadLine(); 

      var ps = new PatternSearch<char>(needle.ToCharArray()); 

      Console.WriteLine(); 
      Console.WriteLine(); 

      Console.WriteLine(hayStack); 

      var matches = ps.Matches(hayStack.ToCharArray()).ToList(); 

      for (int i = 0; i < hayStack.Length; i++) 
       Console.Write(matches.Contains(i) ? "↑" : " "); 

      Console.WriteLine(); 

      Console.ReadLine(); 
     } 
    } 

    /// <summary>Implements a pattern searching algorithm with <b>O(nm)</b> worst-case performance.</summary> 
    /// <typeparam name="T">The data type of the array to search.</typeparam> 
    public class PatternSearch<T> 
    { 
     private struct MatchInfo 
     { 
      public MatchInfo(int startIndex, int matchLength) 
      { 
       this.StartIndex = startIndex; 
       this.MatchLength = matchLength; 
      } 
      public int StartIndex; 
      public int MatchLength; 
     } 

     private IEnumerable<T> pattern; 
     private List<MatchInfo> found; 
     private Func<T, T, bool> eqComp; 

     //optimization for IEnumerables that do not implement IList 
     int patLen = -1; 
     int seqLen = -1; 

     /// <summary>Initializes a new instance of the <see cref="PatternSearch{T}" /> class.</summary> 
     /// <param name="pattern">The pattern that will be searched for.</param> 
     public PatternSearch(T[] pattern) : this(pattern, (x, y) => x.Equals(y)) { } 

     /// <summary> 
     /// Initializes a new instance of the <see cref="PatternSearch{T}"/> class with the specified equality comparer. 
     /// </summary> 
     /// <param name="pattern">The pattern to be searched for.</param> 
     /// <param name="equalityComparer">The equality comparer to use for matching elements in the array.</param> 
     public PatternSearch(T[] pattern, Func<T, T, bool> equalityComparer) 
     { 
      patLen = pattern.Length; 

      if (pattern == null) 
       throw new ArgumentNullException("pattern", "The search pattern cannot be null."); 
      if (equalityComparer == null) 
       throw new ArgumentNullException("equalityComparer", "The equality comparer cannot be null."); 

      if (patLen <= 0) 
       throw new ArgumentException("pattern", "The pattern cannot be empty."); 

      // assign the values 
      this.pattern = pattern; 
      found = new List<MatchInfo>(); 
      eqComp = equalityComparer; 
     } 

     /// <summary> 
     /// Returns the start index of all occurrences of the search pattern within the specified array. 
     /// </summary> 
     /// <param name="seq">The larger sequence to find occurrences of the search pattern within.</param> 
     public IEnumerable<int> Matches(IEnumerable<T> seq) 
     { 
      seqLen = seqLen == -1 ? seq.Count() : seqLen; 
      return this.Matches(seq, 0, seqLen); 
     } 

     /// <summary> 
     /// Returns the start index of all occurrences of the search pattern within the specified array. 
     /// </summary> 
     /// <param name="seq">The larger sequence to find occurrences of the search pattern within.</param> 
     /// <param name="startIndex">The index in <paramref name="seq"/> to start searching at.</param> 
     public IEnumerable<int> Matches(IEnumerable<T> seq, int startIndex) 
     { 
      seqLen = seqLen == -1 ? seq.Count() : seqLen; 
      return this.Matches(seq, startIndex, seqLen); 
     } 

     /// <summary> 
     /// Returns the start index of all occurrences of the search pattern within the specified array. 
     /// </summary> 
     /// <param name="seq">The larger sequence to find occurrences of the search pattern within.</param> 
     /// <param name="count">The maximum number of items in <paramref name="seq"/> to match.</param> 
     public IEnumerable<int> Matches(IEnumerable<T> seq, int startIndex, int count) 
     { 
      patLen = patLen == -1 ? pattern.Count() : patLen; 
      seqLen = seqLen == -1 ? seq.Count() : seqLen; 
      bool addedNew = false; 

      var endPoint = Math.Min(seqLen, startIndex + count); 

      if (seq == null ||      // sequence cannot be null 
       seqLen < patLen ||     // pattern cannot be longer than sequence 
       (endPoint - startIndex) < patLen) // start to end cannot be less than pattern 
       yield break; 

      for (int i = startIndex; i < endPoint; i++) 
      { 
       addedNew = false; 

       // add the first item if a match is found 
       if (eqComp(seq.ElementAt(i), pattern.ElementAt(0))) 
       { 
        if (patLen == 1) 
         yield return i; 

        found.Add(new MatchInfo(i, 1)); 
        addedNew = true; 
       } 

       // check incomplete matches 
       for (int m = found.Count - 1; m >= 0; m--) 
       { 
        //skip the last item added 
        if (addedNew && m == found.Count - 1) 
         continue; 

        var match = found[m]; 

        // check incomplete matches 
        if ((i - match.StartIndex < patLen) && 
         eqComp(seq.ElementAt(i), pattern.ElementAt(match.MatchLength))) 
        { 
         match.MatchLength += 1; 
         found[m] = match; 

         // determine if a complete match has been found 
         if (match.MatchLength == patLen) 
         { 
          yield return match.StartIndex; 
          found.RemoveAt(m); 
         } 
        } 
        else 
         found.RemoveAt(m); 
       } 
      } 
     } 

    } 
} 

Answer 2

최악의 성능은 연속 패턴의 반복 인 경우 O (㎚) (여기서 n = seq.Count)이고, 패턴이 m 회 (I 틀렸다 경우 날 수정) 반복 다른 패턴이다.

List<int> LookFor<T>(IEnumerable<T> seq, T[ ] pattern) 
     where T : IEquatable<T> { 

    var partialMatches = new LinkedList<int>(); 
    var matches = new List<int>(); 

    int i = 0; 
    foreach (T item in seq) { 
     if (item.Equals(pattern[ 0 ])) 
      partialMatches.AddLast(0); 

     var n = partialMatches.First; 
     while(n != null) { 
      if (item.Equals(pattern[ n.Value ])) { 
       n.Value += 1; 
       if (n.Value == pattern.Length) { 
        matches.Add(i - pattern.Length + 1); 

        var next = n.Next; 
        partialMatches.Remove(n); 
        n = next; 

        continue; 
       } 
      } 
      else partialMatches.Remove(n); 

      n = n.Next; 
     } 

     i += 1; 
    } 

    return matches; 
} 

테스트 :

이

void Main() 
{ 
    var matches = LookFor("abcabcabcabcabcabcabc", 
     new char[ ] { 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c' }); 

    foreach (var x in matches) 
     Console.WriteLine("{0}", x); 
} 

출력 :

0 
3 
6 
9 
12