byte[] array pattern search

Question

Anyone know a good and effective way to search/match for a byte pattern in an byte[] array and then return the positions.

For example

byte[] pattern = new byte[] {12,3,5,76,8,0,6,125};

byte[] toBeSearched = new byte[] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,122,22,4,7,89,76,64,12,3,5,76,8,0,6,125}

Answer 1

My solution:

class Program
{
    public static void Main()
    {
        byte[] pattern = new byte[] {12,3,5,76,8,0,6,125};

        byte[] toBeSearched = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125};

        List<int> positions = SearchBytePattern(pattern, toBeSearched);

        foreach (var item in positions)
        {
            Console.WriteLine("Pattern matched at pos {0}", item);
        }

    }

    static public List<int> SearchBytePattern(byte[] pattern, byte[] bytes)
    {
        List<int> positions = new List<int>();
        int patternLength = pattern.Length;
        int totalLength = bytes.Length;
        byte firstMatchByte = pattern[0];
        for (int i = 0; i < totalLength; i++)
        {
            if (firstMatchByte == bytes[i] && totalLength - i >= patternLength)
            {
                byte[] match = new byte[patternLength];
                Array.Copy(bytes, i, match, 0, patternLength);
                if (match.SequenceEqual<byte>(pattern))
                {
                    positions.Add(i);
                    i += patternLength - 1;
                }
            }
        }
        return positions;
    }
}

Answer 2

I tried various solutions and ended up modifying the SearchBytePattern one. I tested on a 30k sequence and it is, fast :)

    static public int SearchBytePattern(byte[] pattern, byte[] bytes)
    {
        int matches = 0;
        for (int i = 0; i < bytes.Length; i++)
        {
            if (pattern[0] == bytes[i] && bytes.Length - i >= pattern.Length)
            {
                bool ismatch = true;
                for (int j = 1; j < pattern.Length && ismatch == true; j++)
                {
                    if (bytes[i + j] != pattern[j])
                        ismatch = false;
                }
                if (ismatch)
                {
                    matches++;
                    i += pattern.Length - 1;
                }
            }
        }
        return matches;
    }

Let me know your thoughts.

Answer 3

This is my propossal, more simple and faster:

int Search(byte[] src, byte[] pattern)
{
    int c = src.Length - pattern.Length + 1;
    int j;
    for (int i = 0; i < c; i++)
    {
        if (src[i] != pattern[0]) continue;
        for (j = pattern.Length - 1; j >= 1 && src[i + j] == pattern[j]; j--) ;
        if (j == 0) return i;
    }
    return -1;
}

Answer 4

Here's a simple code i wrote using only basic data types: (It returns the index of first occurance)

private static int findMatch(byte[] data, byte[] pattern) {
    if(pattern.length > data.length){
        return -1;
    }
    for(int i = 0; i<data.length ;){
        int j;
       for(j=0;j<pattern.length;j++){

           if(pattern[j]!=data[i])
               break;
           i++;
       }
       if(j==pattern.length){
           System.out.println("Pattern found at : "+(i - pattern.length ));
           return i - pattern.length ;
       }
       if(j!=0)continue;
       i++;
    }

    return -1;
}

Answer 5

Jb Evain's answer has:

 for (int i = 0; i < self.Length; i++) {
      if (!IsMatch (self, i, candidate))
           continue;
      list.Add (i);
 }

and then the IsMatch function first checks whether candidate goes beyond the length of the array being searched.

This would be more efficient if the for loop were coded:

 for (int i = 0; i < self.Length - candidate.Length; i++) {
      if (!IsMatch (self, i, candidate))
           continue;
      list.Add (i);
 }

at this point one could also eliminate the test from the start of IsMatch, so long as you contract via pre-conditions never to call it with "illegal' parameters.

Answer 6

Why make the simple difficult? This can be done in any language using for loops. Here is one in C#:

using System;
using System.Collections.Generic;

namespace BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            byte[] pattern = new byte[] {12,3,5,76,8,0,6,125};
            byte[] toBeSearched = new byte[] {23,36,43,76,125,56,34,234,12,3,5,76,8,0,6,125,234,56,211,
122,22,4,7,89,76,64,12,3,5,76,8,0,6,125};

            List<int> occurences = findOccurences(toBeSearched, pattern);

            foreach(int occurence in occurences) {
                Console.WriteLine("Found match starting at 0-based index: " + occurence);
            }


        }

        static List<int> findOccurences(byte[] haystack, byte[] needle)
        {
            List<int> occurences = new List<int>();

            for (int i = 0; i < haystack.Length; i++)
            {
                if (needle[0] == haystack[i])
                {
                    bool found = true;
                    int j, k;
                    for (j = 0, k = i; j < needle.Length; j++, k++)
                    {
                        if (k >= haystack.Length || needle[j] != haystack[k])
                        {
                            found = false;
                            break;
                        }
                    }
                    if (found)
                    {
                        occurences.Add(i - 1);
                        i = k;
                    }
                }
            }
            return occurences;
        }
    }
}