Реализовать алгоритм Рабина с использованием хеш функций - C#

Узнай цену своей работы

Формулировка задачи:

Здравствуйте. Необходимо реализовать алгоритм Рабина с использованием хеш функций на языке C#. Нашел в википедии реализацию. Помогите перевести на нужный язык. Спасибо!
function RabinKarp(string s[1..n], string sub[1..m])
   hsub := hash(sub[1..m])
    hs := hash(s[1..m])
      for i from 1 to (n-m+1)
          if hs = hsub
              if s[i..i+m-1] = sub
                  return i
          hs := hash(s[i+1..i+m])
      return not found

Решение задачи: «Реализовать алгоритм Рабина с использованием хеш функций»

textual
Листинг программы
//Хеш-функция для алгоритма Рабина-Карпа
public static int Hash(string x)
        {
            int p = 31; //Простое число
            int rez = 0; //Результат вычисления 
            for (int i = 0; i < x.Length; i++)
            {
                rez += (int)Math.Pow(p,x.Length-1-i)*(int)(x[i]);//Подсчет хеш-функции
            }
            return rez;
        }
//Функция поиска алгоритмом Рабина-Карпа
public static string Rabina(string x, string s)
        {
            string nom = ""; //Номера всех вхождений образца в строку
            if (x.Length > s.Length) return nom; //Если искомая строка больше исходной – возврат пустого поиска
            int xhash = Hash(x); //Вычисление хеш-функции искомой строки
            int shash = Hash(s.Substring(0,x.Length)); //Вычисление хеш-функции первого слова длины образца в строке S
            bool flag;
            int j;
            for (int i = 0; i < s.Length - x.Length; i++)
            {
                if (xhash == shash)//Если значения хеш-функций совпадают
                {
                    flag = true;
                    j = 0;
                    while ((flag == true) && (j < x.Length))
                    {
                        if (x[j] != s[i + j]) flag = false;
                        j++;
                    }
                    if (flag == true) //Если искомая строка совпала с частью исходной
                        nom = nom + Convert.ToString(i) + ", "; //Добавление номера вхождения
                }
                else //Иначе вычисление нового значения хеш-функции
                    shash = (shash - (int)Math.Pow(31,x.Length-1)*(int)(s[i]))*31+(int)(s[i+x.Length]);
            }
            if (nom != "") //Если вхождение найдено
            {
                nom = nom.Substring(0, nom.Length - 2); //Удаление запятой и пробела
            }
            return nom; //Возвращение результата поиска
        }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 3.867 из 5
Похожие ответы