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