Tag: Search

BoyerMooreString.cs

BoyerMoore String Searching Algorithm

using System;
using System.Collections.Generic;
public class BoyerMooreString
{
    private       int[]  _jumpTable;
    private       string _pattern;
    private       int    _patternLength;
    public BoyerMooreString()
    {
    }
    public BoyerMooreString(string pattern)
    {
        SetPattern(pattern);
    }
    public void SetPattern(string pattern)
    {
        _pattern       = pattern;
        _jumpTable     = new int[ushort.MaxValue];
        _patternLength = _pattern.Length;
        for (var index = 0; index < ushort.MaxValue; ++index)
            _jumpTable[index] = _patternLength;
        for (var index = 0; index < _patternLength - 1; ++index)
            _jumpTable[_pattern[index]] = _patternLength - index - 1;
    }
    public unsafe int Search(string searray, int startIndex = 0)
    {
        if (_pattern == null)
            throw new Exception("Pattern has not been set.");
        if (_patternLength > searray.Length)
            throw new Exception("Search Pattern length exceeds search array length.");
        var num1 = startIndex;
        var num2 = searray.Length - _patternLength;
        var num3 = _patternLength - 1;
        var num4 = 0;
        fixed (char* chPtr1 = searray)
        {
            var chPtr2 = chPtr1 + startIndex;
            fixed (char* chPtr3 = _pattern)
            {
                while (num1 <= num2)
                {
                    var index = num3;
                    while (index >= 0 && chPtr3[index] == chPtr2[num1 + index])
                        --index;
                    if (index < 0)
                        return num1;
                    num1 += _jumpTable[chPtr2[num1 + index]];
                    ++num4;
                }
            }
        }
        return -1;
    }
    public unsafe (List<int>, int) SearchAll(string searray, int startIndex = 0)
    {
        if (_pattern == null)
            throw new Exception("Pattern has not been set.");
        if (_patternLength > searray.Length)
            throw new Exception("Search Pattern length exceeds search array length.");
        var num1    = startIndex;
        var num2    = searray.Length - _patternLength;
        var num3    = _patternLength - 1;
        var intList = new List<int>();
        var num4    = 0;
        fixed (char* chPtr1 = searray)
        {
            var chPtr2 = chPtr1 + startIndex;
            fixed (char* chPtr3 = _pattern)
            {
                while (num1 <= num2)
                {
                    var index = num3;
                    while (index >= 0 && chPtr3[index] == chPtr2[num1 + index])
                        --index;
                    if (index < 0)
                        intList.Add(num1);
                    num1 += _jumpTable[chPtr2[num1 + index]];
                    ++num4;
                }
            }
        }
        return (intList, num4);
    }
    public int SuperSearch(string searray, int nth, int start = 0)
    {
        var startIndex = start;
        var num1       = 0;
        do
        {
            var num2 = Search(searray, startIndex);
            if (num2 == -1)
                return -1;
            ++num1;
            startIndex = num2 + 1;
        } while (num1 < nth);
        return startIndex - 1;
    }
    public class BMPartialPatternSearchString
    {
        public int MinimumSearchLength;
        public BMPartialPatternSearchString(int min = 5)
        {
            MinimumSearchLength = min;
        }
        public (string partialPattern, int idx) SearchPartial(string pattern, string searray)
        {
            BoyerMooreString boyerMooreString = new BoyerMooreString(pattern);
            var              length           = pattern.Length;
            var              stringList       = new List<string>();
            if (length < MinimumSearchLength)
                throw new Exception("Search Pattern less than minimum search length.");
            var startIndex          = 0;
            var minimumSearchLength = MinimumSearchLength;
            do
            {
                var pattern1 = pattern.Substring(startIndex, minimumSearchLength);
                stringList.Add(pattern1);
                boyerMooreString.SetPattern(pattern1);
                int num = boyerMooreString.Search(searray);
                if (num != -1)
                    return (pattern1, num);
                if (startIndex + minimumSearchLength >= length)
                {
                    startIndex = 0;
                    ++minimumSearchLength;
                }
                else
                {
                    ++startIndex;
                }
            } while (minimumSearchLength != length + 1);
            return (pattern, -1);
        }
        public List<(string partialPattern, int idx)> SearchPartialFirst(
            string pattern,
            string searray)
        {
            BoyerMooreString boyerMooreString = new BoyerMooreString(pattern);
            var              length           = pattern.Length;
            var              valueTupleList   = new List<(string, int)>();
            var              stringList       = new List<string>();
            if (length < MinimumSearchLength)
                throw new Exception("Search Pattern less than minimum search length.");
            var startIndex          = 0;
            var minimumSearchLength = MinimumSearchLength;
            do
            {
                var pattern1 = pattern.Substring(startIndex, minimumSearchLength);
                stringList.Add(pattern1);
                boyerMooreString.SetPattern(pattern1);
                int num = boyerMooreString.Search(searray);
                if (num != -1)
                    valueTupleList.Add((pattern1, num));
                if (startIndex + minimumSearchLength >= length)
                {
                    startIndex = 0;
                    ++minimumSearchLength;
                }
                else
                {
                    ++startIndex;
                }
            } while (minimumSearchLength != length + 1);
            return new List<(string, int)>
                { (pattern, -1) };
        }
        public List<(string partialPattern, int idx)> SearchPartialAll(
            string pattern,
            string searray)
        {
            BoyerMooreString boyerMooreString = new BoyerMooreString(pattern);
            var              length           = pattern.Length;
            var              valueTupleList   = new List<(string, int)>();
            var              stringList       = new List<string>();
            if (length < MinimumSearchLength)
                throw new Exception("Search Pattern less than minimum search length.");
            var startIndex          = 0;
            var minimumSearchLength = MinimumSearchLength;
            do
            {
                var pattern1 = pattern.Substring(startIndex, minimumSearchLength);
                stringList.Add(pattern1);
                boyerMooreString.SetPattern(pattern1);
                (List<int>, int) tuple = boyerMooreString.SearchAll(searray);
                if (tuple.Item1.Count > 0)
                    foreach (var num in tuple.Item1)
                        valueTupleList.Add((pattern1, num));
                if (startIndex + minimumSearchLength >= length)
                {
                    startIndex = 0;
                    ++minimumSearchLength;
                }
                else
                {
                    ++startIndex;
                }
            } while (minimumSearchLength != length + 1);
            return valueTupleList;
        }
    }
}

BoyerMooreGeneric.cs

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;
    }
}