Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace ClassLibrary1
- {
- public class Mur : ISubstringSearch {
- public List<int> FindAll(string text, string substring)
- {
- List<int> res = new List<int>();
- char[] pattern = substring.ToCharArray();
- char[] textChAr = text.ToCharArray();
- if (pattern.Length > textChAr.Length)
- {
- return res;
- }
- byte[] StopSymbols = BuildStopCharTable(pattern);
- byte[] Suffixes = BuildSuffixTable(pattern);
- int offset = 0;
- int scan;
- int last = pattern.Length - 1;
- int maxoffset = textChAr.Length - pattern.Length;
- while (offset <= maxoffset)
- {
- scan = last;
- bool fl = true;
- while (pattern[scan] == textChAr[scan + offset])
- {
- scan--;
- if (scan < 0)
- {
- res.Add(offset);
- fl = false;
- offset += Math.Max(StopSymbols[textChAr[offset + last]], Suffixes[pattern.Length]);
- break;
- }
- }
- if (fl)
- offset += Math.Max(StopSymbols[textChAr[offset + last]], Suffixes[scan + 1]);
- }
- return res;
- }
- private static byte[] BuildStopCharTable(char[] pattern)
- {
- byte[] StopSymbols = new byte[0x10000];
- for (int i = 0; i < StopSymbols.Length; i++)
- {
- StopSymbols[i] = (byte)pattern.Length;
- }
- int last = pattern.Length - 1;
- for (int i = 0; i < last; i++)
- {
- StopSymbols[pattern[i]] = (byte)(last - i);
- }
- return StopSymbols;
- }
- private byte[] BuildSuffixTable(char[] pattern)
- {
- byte[] suffixes = new byte[pattern.Length + 1];
- for (int i = 0; i < pattern.Length; i++)
- {
- suffixes[i] = (byte)pattern.Length;
- }
- suffixes[pattern.Length] = 1;
- StringBuilder sb1 = new StringBuilder();
- StringBuilder sb2 = new StringBuilder();
- for (int i = pattern.Length - 1; i >= 0; i--)
- {
- for (int at = i; at < pattern.Length; at++)
- {
- for (int k = at; k < pattern.Length; k++)
- {
- sb1.Append(pattern[k]);
- }
- for (int j = at - 1; j >= 0; j--)
- {
- for (int k = j; k < j + sb1.Length; k++)
- {
- sb2.Append(pattern[k]);
- }
- bool fl = true;
- for (int k = 0; k < sb1.Length; k++)
- {
- if (sb1[k] != sb2[k])
- {
- fl = false;
- break;
- }
- }
- if (fl)
- {
- suffixes[i] = (byte)(at - j);
- sb2.Clear();
- break;
- }
- sb2.Clear();
- }
- sb1.Clear();
- }
- }
- return suffixes;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement