C# Boyer Moore Generic Search Algorithm<\/p>\n\n\n\n
Updated: March 13, 2022<\/p>\n\n\n\n
using System;\nusing System.Collections.Generic;\npublic class BoyerMooreGeneric<T>\n{\n private readonly IEqualityComparer<T> _comparer;\n private Dictionary<T, int> _jumpTable;\n private T[] _pattern;\n private int _patternLength;\n public BoyerMooreGeneric()\n {\n _comparer = EqualityComparer<T>.Default;\n }\n public BoyerMooreGeneric(T[] pattern)\n {\n _comparer = EqualityComparer<T>.Default;\n SetPattern(pattern);\n }\n public BoyerMooreGeneric(T[] pattern, IEqualityComparer<T> comparer)\n {\n if (comparer == null)\n _comparer = EqualityComparer<T>.Default;\n else\n _comparer = comparer;\n SetPattern(pattern);\n }\n public BoyerMooreGeneric(IEqualityComparer<T> comparer)\n {\n if (comparer == null)\n _comparer = EqualityComparer<T>.Default;\n else\n _comparer = comparer;\n }\n public void SetPattern(T[] pattern)\n {\n _pattern = pattern;\n _jumpTable = new Dictionary<T, int>();\n _patternLength = _pattern.Length;\n for (var index = 0; index < _patternLength - 1; index++)\n _jumpTable[_pattern[index]] = _patternLength - index - 1;\n }\n public int Search(T[] searchArray, int startIndex = 0)\n {\n if (_pattern == null)\n throw new Exception(\"Pattern has not been set.\");\n if (_patternLength > searchArray.Length)\n throw new Exception(\"Search Pattern length exceeds search array length.\");\n var scArr = searchArray.SubArray(startIndex, searchArray.Length - startIndex);\n var index = startIndex;\n var limit = searchArray.Length - _patternLength;\n var patternLengthMinusOne = _patternLength - 1;\n var Moves = 0;\n var a0 = 0;\n var b0 = 0;\n while (index <= limit)\n {\n var j = patternLengthMinusOne;\n while (j >= 0 && _comparer.Equals(_pattern[j], scArr[index + j]))\n j--;\n if (j < 0)\n return index;\n if (_jumpTable.TryGetValue(scArr[index + j], out var j0))\n {\n index += j0;\n a0++;\n }\n else\n {\n index += _patternLength;\n b0++;\n }\n Moves++;\n }\n return -1;\n }\n public List<int> SearchAll(T[] searchArray, int startIndex = 0)\n {\n if (searchArray == null)\n throw new Exception(\"Search array has not been set.\");\n if (_pattern == null)\n throw new Exception(\"Pattern has not been set.\");\n var scArr = searchArray.SubArray(startIndex, searchArray.Length - startIndex);\n var scLen = searchArray.Length;\n if (_patternLength > scArr.Length)\n throw new Exception(\"Search Pattern length exceeds search array length.\");\n var index = 0;\n var lst = new List<int>();\n while (index <= scLen - _patternLength)\n {\n var j = _patternLength - 1;\n while (j >= 0 && _comparer.Equals(_pattern[j], scArr[index + j]))\n j--;\n if (j < 0)\n lst.Add(index);\n if (_jumpTable.TryGetValue(scArr[index + j], out var j0))\n index += j0;\n else\n index += _patternLength;\n }\n return lst;\n }\n public int SuperSearch(T[] searchArray, int nth, int start = 0)\n {\n var e = start;\n var c = 0;\n do\n {\n e = Search(searchArray, e);\n if (e == -1)\n return -1;\n c++;\n e++;\n } while (c < nth);\n return e - 1;\n }\n public IEnumerable<(T[] partialPattern, int idx)> SearchPartialAll(T[] pattern, T[] searchArray, int MinimumSearchLength = 3)\n {\n SetPattern(pattern);\n var len = searchArray.Length;\n var lst = new List<(T[] partialPattern, int idx)>();\n if (len < MinimumSearchLength)\n throw new Exception(\"Search Pattern less than minimum search length.\");\n var offset = 0;\n var wl = MinimumSearchLength;\n var pDic = new Dictionary<int, int>();\n int ol = 0, il = 0;\n do\n {\n ol++;\n var tpat = new T[wl];\n Array.Copy(searchArray, offset, tpat, 0, wl);\n SetPattern(tpat);\n var idxl = SearchAll(searchArray);\n if (idxl.Count > 0)\n foreach (var idx in idxl)\n lst.Add((tpat, idx));\n if (pDic.ContainsKey(wl))\n pDic[wl] += idxl.Count;\n else\n pDic.Add(wl, idxl.Count);\n if (offset + wl >= len)\n {\n il++;\n if (pDic.ContainsKey(wl))\n if (pDic[wl] == 0)\n {\n pDic.Remove(wl);\n break;\n }\n offset = 0;\n ol = 0;\n wl++;\n continue;\n }\n offset++;\n } while (wl != len + 1);\n return lst;\n }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"C# Boyer Moore Generic Search Algorithm Updated: March 13, 2022<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[161,228,46,101],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/523"}],"collection":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/comments?post=523"}],"version-history":[{"count":2,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/523\/revisions"}],"predecessor-version":[{"id":530,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/523\/revisions\/530"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=523"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=523"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=523"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}