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