stroki

using System;
using System.Collections.Generic;

namespace Searches
{
    public class BruteForce : ISubstringSearch
    {
        public List<int> search(string text, string searchtext)
        {
            List<int> pozition = new List<int>();
            int length = searchtext.Length;
            for (int i = 0; length <= text.Length; i++)
            {

                if (text[i..length] == searchtext)
                {
                    pozition.Add(i);
                }
                length++;
            }
            return pozition;
        }
    }
    public class KMP : ISubstringSearch
    {
        public List<int> search(string text, string searchtext)
        {
            int[] pf = GetPrefix(searchtext);
            int i = 0;
            int j = 0;
            int m = searchtext.Length;
            int n = text.Length;
            List<int> pozition = new List<int>();
            while (i < n)
            {
                if (text[i] == searchtext[j])
                {
                    i++;
                    j++;
                    if (j == m)
                    {
                        pozition.Add(i - j);

                        i = i - j + 1; j = 0;
                    }
                }
                else
                    if (j > 0)
                    j = pf[j - 1];
                else
                    i++;
            }

            return pozition;
        }
        private int[] GetPrefix(string s)
        {
            int[] result = new int[s.Length];
            result[0] = 0;
            int j = 0;
            int i = 1;
            while (i < s.Length)
            {
                if (s[j] == s[i])
                {
                    result[i] = j + 1;
                    i++;
                    j++;
                }
                else
                    if (j == 0)
                {
                    result[i] = 0;
                    i++;
                }
                else
                    j = result[j - 1];
            }
            return result;
        }
    }
    public class BoyerMoore : ISubstringSearch
    {
        public List<int> search(string text, string searchtext)
        {

            int s = 0;
            int m = searchtext.Length;
            int n = text.Length;
            List<int> result = new List<int>();
            Dictionary<char, int> bad = new Dictionary<char, int>();
            int[] bpos = new int[m + 1]; int[] shift = new int[m + 1];

            for (int i = 0; i < m + 1; i++) shift[i] = 0;

            bad = badCharHeuristic(searchtext);
            preprocess_strong_suffix(shift, bpos, searchtext, m);


            int j, bound = 0;
            for (int i = 0; i <= n - m;)
            {
                for (j = m - 1; j >= bound && searchtext[j] == text[i + j]; j--) ;
                if (j < bound)
                {
                    result.Add(i);
                    bound = m - shift[0];
                    j = -1; }
                else
                {
                    bound = 0;
                }
                if (j < bound) i += shift[j + 1];
                else
                if (j == m - 1)
                {
                    if (bad.ContainsKey(text[i + j]))
                        i += Math.Max(shift[j + 1], bad[text[i + j]]);
                    else
                        i += Math.Max(shift[j + 1], bad['*']);
                }
                else
                {
                    if (bad.ContainsKey(text[i + j]))
                        i += Math.Max(shift[j + 1], j - bad[text[i + j]]);
                    else
                        i += Math.Max(shift[j + 1], j - bad['*']);
                }
            }
            return result;
        }
        static void preprocess_strong_suffix(int[] shift, int[] bpos,
                              string pat, int m)
        {
            for (int i = 0; i < m + 1; i++)
            {
                shift[i] = m;
            }
            for (int i = 0; i < m; i++)
            {
                bpos[i] = 0;
            }
            for (int j = 1, maxZidx = 0, maxZ = 0; j < m; j++)
            {
                if (j <= maxZ) bpos[j] = Math.Min(maxZ - j + 1, bpos[j - maxZidx]);
                while (j + bpos[j] < m && pat[m - 1 - bpos[j]] == pat[m - 1 - (j + bpos[j])]) bpos[j]++;
                if (j + bpos[j] - 1 > maxZ)
                {
                    maxZidx = j;
                    maxZ = j + bpos[j] - 1;
                }
            }
            for (int j = m - 1; j > 0; j--) shift[m - bpos[j]] = j;
            for (int j = 1, r = 0; j <= m - 1; j++)
                if (j + bpos[j] == m)
                    for (; r <= j; r++)
                        if (shift[r] == m) shift[r] = j;

        }
        private Dictionary<char, int> badCharHeuristic(string searchstring)
        {
            int m = searchstring.Length;
            Dictionary<char, int> result = new Dictionary<char, int>();
            int count = 1;
            for (int i = m - 2; i >= 0; i--)
            {
                if (!result.ContainsKey(searchstring[i]))
                {
                    result.Add(searchstring[i], count);
                    count++;
                }
            }
            if (!result.ContainsKey(searchstring[m - 1]))
                result.Add(searchstring[m - 1], m);
            result.Add('*', m);
            return result;
        }
    }

}