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