Tag: Generic

C# Boyer Moore Generic Search Algorithm

Updated: March 13, 2022

using System;
using System.Collections.Generic;
public class BoyerMooreGeneric<T>
{
    private readonly IEqualityComparer<T> _comparer;
    private          Dictionary<T, int>   _jumpTable;
    private          T[]                  _pattern;
    private          int                  _patternLength;
    public BoyerMooreGeneric()
    {
        _comparer = EqualityComparer<T>.Default;
    }
    public BoyerMooreGeneric(T[] pattern)
    {
        _comparer = EqualityComparer<T>.Default;
        SetPattern(pattern);
    }
    public BoyerMooreGeneric(T[] pattern, IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            _comparer = EqualityComparer<T>.Default;
        else
            _comparer = comparer;
        SetPattern(pattern);
    }
    public BoyerMooreGeneric(IEqualityComparer<T> comparer)
    {
        if (comparer == null)
            _comparer = EqualityComparer<T>.Default;
        else
            _comparer = comparer;
    }
    public void SetPattern(T[] pattern)
    {
        _pattern       = pattern;
        _jumpTable     = new Dictionary<T, int>();
        _patternLength = _pattern.Length;
        for (var index = 0; index < _patternLength - 1; index++)
            _jumpTable[_pattern[index]] = _patternLength - index - 1;
    }
    public int Search(T[] searchArray, int startIndex = 0)
    {
        if (_pattern == null)
            throw new Exception("Pattern has not been set.");
        if (_patternLength > searchArray.Length)
            throw new Exception("Search Pattern length exceeds search array length.");
        var scArr                 = searchArray.SubArray(startIndex, searchArray.Length - startIndex);
        var index                 = startIndex;
        var limit                 = searchArray.Length - _patternLength;
        var patternLengthMinusOne = _patternLength     - 1;
        var Moves                 = 0;
        var a0                    = 0;
        var b0                    = 0;
        while (index <= limit)
        {
            var j = patternLengthMinusOne;
            while (j >= 0 && _comparer.Equals(_pattern[j], scArr[index + j]))
                j--;
            if (j < 0)
                return index;
            if (_jumpTable.TryGetValue(scArr[index + j], out var j0))
            {
                index += j0;
                a0++;
            }
            else
            {
                index += _patternLength;
                b0++;
            }
            Moves++;
        }
        return -1;
    }
    public List<int> SearchAll(T[] searchArray, int startIndex = 0)
    {
        if (searchArray == null)
            throw new Exception("Search array has not been set.");
        if (_pattern == null)
            throw new Exception("Pattern has not been set.");
        var scArr = searchArray.SubArray(startIndex, searchArray.Length - startIndex);
        var scLen = searchArray.Length;
        if (_patternLength > scArr.Length)
            throw new Exception("Search Pattern length exceeds search array length.");
        var index = 0;
        var lst   = new List<int>();
        while (index <= scLen - _patternLength)
        {
            var j = _patternLength - 1;
            while (j >= 0 && _comparer.Equals(_pattern[j], scArr[index + j]))
                j--;
            if (j < 0)
                lst.Add(index);
            if (_jumpTable.TryGetValue(scArr[index + j], out var j0))
                index += j0;
            else
                index += _patternLength;
        }
        return lst;
    }
    public int SuperSearch(T[] searchArray, int nth, int start = 0)
    {
        var e = start;
        var c = 0;
        do
        {
            e = Search(searchArray, e);
            if (e == -1)
                return -1;
            c++;
            e++;
        } while (c < nth);
        return e - 1;
    }
    public IEnumerable<(T[] partialPattern, int idx)> SearchPartialAll(T[] pattern, T[] searchArray, int MinimumSearchLength = 3)
    {
        SetPattern(pattern);
        var len = searchArray.Length;
        var lst = new List<(T[] partialPattern, int idx)>();
        if (len < MinimumSearchLength)
            throw new Exception("Search Pattern less than minimum search length.");
        var offset = 0;
        var wl     = MinimumSearchLength;
        var pDic   = new Dictionary<int, int>();
        int ol     = 0, il = 0;
        do
        {
            ol++;
            var tpat = new T[wl];
            Array.Copy(searchArray, offset, tpat, 0, wl);
            SetPattern(tpat);
            var idxl = SearchAll(searchArray);
            if (idxl.Count > 0)
                foreach (var idx in idxl)
                    lst.Add((tpat, idx));
            if (pDic.ContainsKey(wl))
                pDic[wl] += idxl.Count;
            else
                pDic.Add(wl, idxl.Count);
            if (offset + wl >= len)
            {
                il++;
                if (pDic.ContainsKey(wl))
                    if (pDic[wl] == 0)
                    {
                        pDic.Remove(wl);
                        break;
                    }
                offset = 0;
                ol     = 0;
                wl++;
                continue;
            }
            offset++;
        } while (wl != len + 1);
        return lst;
    }
}