Tag: Algorithm

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