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.Reflection;
- using System.Text;
- using System.Threading.Tasks;
- namespace ClassLibrary1
- {
- public class KnutMorrisPratt : ISubstringSearch {
- int[] PrefixFunctionFast(string str)
- {
- int[] result = new int[str.Length];
- result[0] = 0;
- for (int i = 1; i < str.Length; i++)
- {
- int k = result[i - 1];
- while (k > 0 && str[k] != str[i])
- {
- k = result[k - 1];
- }
- if (str[k] == str[i])
- {
- k++;
- }
- result[i] = k;
- }
- return result;
- }
- int[] PrefixFunction(string str) {
- int n = str.Length;
- int[] p = new int[n];
- for (int i = 0; i < n; i++)
- {
- for (int k = 0; k < i; k++)
- {
- bool fl = true;
- for (int j = 0; j < k + 1; j++)
- {
- if (str[j] != str[i - k + j])
- {
- fl = false;
- break;
- }
- }
- if (fl)
- p[i] = (byte)(k + 1);
- }
- }
- return p;
- }
- public List<int> FindAll(string text, string substring) {
- List<int> res = new List<int>();
- int[] prefix_sub = PrefixFunctionFast(substring);
- int k = 0;
- for(int i = 0; i < text.Length; i++)
- {
- while (k > 0 && substring[k] != text[i]) { k = prefix_sub[k - 1]; }
- if (substring[k] == text[i]) k++;
- if (k == substring.Length)
- {
- res.Add(i - k + 1);
- k = prefix_sub[k - 1];
- }
- }
- return res;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement