Реализовать алгоритм Рабина с использованием хеш функций - 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; //Возвращение результата поиска }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д