Advertisement
Pearlfromsu

boyer moore algorithm c#

May 6th, 2024
855
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.71 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace ClassLibrary1
  8. {
  9.     public class Mur : ISubstringSearch {
  10.  
  11.         public List<int> FindAll(string text, string substring)
  12.         {
  13.             List<int> res = new List<int>();
  14.             char[] pattern = substring.ToCharArray();
  15.             char[] textChAr = text.ToCharArray();
  16.             if (pattern.Length > textChAr.Length)
  17.             {
  18.                 return res;
  19.             }
  20.             byte[] StopSymbols = BuildStopCharTable(pattern);
  21.             byte[] Suffixes = BuildSuffixTable(pattern);
  22.             int offset = 0;
  23.             int scan;
  24.             int last = pattern.Length - 1;
  25.             int maxoffset = textChAr.Length - pattern.Length;
  26.             while (offset <= maxoffset)
  27.             {
  28.                 scan = last;
  29.                 bool fl = true;
  30.                 while (pattern[scan] == textChAr[scan + offset])
  31.                 {
  32.                     scan--;
  33.                     if (scan < 0)
  34.                     {
  35.                         res.Add(offset);
  36.                         fl = false;
  37.                         offset += Math.Max(StopSymbols[textChAr[offset + last]], Suffixes[pattern.Length]);
  38.                         break;
  39.                     }
  40.                 }
  41.                 if (fl)
  42.                     offset += Math.Max(StopSymbols[textChAr[offset + last]], Suffixes[scan + 1]);              
  43.             }
  44.             return res;
  45.         }
  46.         private static byte[] BuildStopCharTable(char[] pattern)
  47.         {
  48.             byte[] StopSymbols = new byte[0x10000];
  49.             for (int i = 0; i < StopSymbols.Length; i++)
  50.             {
  51.                 StopSymbols[i] = (byte)pattern.Length;
  52.             }
  53.             int last = pattern.Length - 1;
  54.             for (int i = 0; i < last; i++)
  55.             {
  56.                 StopSymbols[pattern[i]] = (byte)(last - i);
  57.             }
  58.             return StopSymbols;
  59.         }
  60.         private byte[] BuildSuffixTable(char[] pattern)
  61.         {
  62.             byte[] suffixes = new byte[pattern.Length + 1];
  63.             for (int i = 0; i < pattern.Length; i++)
  64.             {
  65.                 suffixes[i] = (byte)pattern.Length;
  66.             }
  67.             suffixes[pattern.Length] = 1;
  68.             StringBuilder sb1 = new StringBuilder();
  69.             StringBuilder sb2 = new StringBuilder();
  70.             for (int i = pattern.Length - 1; i >= 0; i--)
  71.             {
  72.                 for (int at = i; at < pattern.Length; at++)
  73.                 {
  74.                     for (int k = at; k < pattern.Length; k++)
  75.                     {
  76.                         sb1.Append(pattern[k]);
  77.                     }
  78.                     for (int j = at - 1; j >= 0; j--)
  79.                     {
  80.                         for (int k = j; k < j + sb1.Length; k++)
  81.                         {
  82.                             sb2.Append(pattern[k]);
  83.                         }
  84.                         bool fl = true;
  85.                         for (int k = 0; k < sb1.Length; k++)
  86.                         {
  87.                             if (sb1[k] != sb2[k])
  88.                             {
  89.                                 fl = false;
  90.                                 break;
  91.                             }
  92.                         }
  93.                         if (fl)
  94.                         {
  95.                             suffixes[i] = (byte)(at - j);
  96.                             sb2.Clear();
  97.                             break;
  98.                         }
  99.                         sb2.Clear();
  100.                     }
  101.                     sb1.Clear();
  102.                 }
  103.             }
  104.             return suffixes;
  105.         }
  106.     }
  107. }
  108.    
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement