Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Text;
- using System.Diagnostics;
- namespace ConsoleApp5
- {
- class Program
- {
- public static string GenRandomString(string Alphabet, int Length)
- {
- Random rnd = new Random();
- StringBuilder sb = new StringBuilder(Length - 1);
- int Position = 0;
- for (int i = 0; i < Length; i++)
- {
- Position = rnd.Next(0, Alphabet.Length - 1);
- sb.Append(Alphabet[Position]);
- }
- return sb.ToString();
- }
- public static void RabinKarp1(string t, string s)
- {
- const long P = 37;
- //вычисляем массив степеней P
- long[] pwp = new long[t.Length];
- pwp[0] = 1;
- for (int i = 1; i < t.Length; i++)
- {
- pwp[i] = pwp[i - 1] * P;
- }
- //вычисляем массив хэш-значение для всех префиксов строки T
- long[] h = new long[t.Length];
- for (int i = 0; i < t.Length; i++)
- {
- h[i] = (t[i] - 'a' + 1) * pwp[i]; //1
- if (i > 0)
- h[i] += h[i - 1];
- }
- // вычисляем хэш-значение для подстроки S
- long h_s = 0;
- for (int i = 0; i < s.Length; i++)
- {
- h_s += (s[i] - 'a' + 1) * pwp[i];
- }
- //проводим поиск по хеш-значениям
- for (int i = 0; i + s.Length - 1 < t.Length; i++)
- {
- // находим хэш-значение подстроки T начиная с позиции i длиною s.Length
- long cur_h = h[i + s.Length - 1];
- if (i > 0)
- {
- cur_h -= h[i - 1];
- }
- //приводим хэш-значения двух подстрок к одной степени
- if (cur_h == h_s * pwp[i]) // если хеш-значения равны, то и подстроки равны
- {
- Console.Write("{0} ", i); // выводим позицию i, с которой начинается повторение
- }
- }
- }
- public static void RabinKarp(string t, string s)
- {
- const long P = 37;
- //вычисляем массив степеней P
- long[] pwp = new long[t.Length];
- pwp[0] = 1;
- for (int i = 1; i < t.Length; i++)
- {
- pwp[i] = pwp[i - 1] * P;
- }
- //вычисляем массив хэш-значение для всех префиксов строки T
- long[] h = new long[t.Length];
- for (int i = 0; i < t.Length; i++)
- {
- h[i] = (t[i] - 'a' + 1) * pwp[i]; //1
- if (i > 0)
- h[i] += h[i - 1];
- }
- // вычисляем хэш-значение для подстроки S
- long h_s = 0;
- for (int i = 0; i < s.Length; i++)
- {
- h_s += (s[i] - 'a' + 1) * pwp[i];
- }
- //проводим поиск по хеш-значениям
- for (int i = 0; i + s.Length - 1 < t.Length; i++)
- {
- // находим хэш-значение подстроки T начиная с позиции i длиною s.Length
- long cur_h = h[i + s.Length - 1];
- if (i > 0)
- {
- cur_h -= h[i - 1];
- }
- //приводим хэш-значения двух подстрок к одной степени
- if (cur_h == h_s * pwp[i]) // если хеш-значения равны, то и подстроки равны
- {
- Console.Write("{0} ", i); // выводим позицию i, с которой начинается повторение
- }
- }
- }
- static void Main(string[] args)
- {
- string ran1 = GenRandomString("ПРИТОНПРИТОНПРИТОНПРИТОНПРИТОНПРИТОНПРИТОНПРИТОН", 10000);
- string ran2 = GenRandomString("ПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕ", 3);
- string ran3 = GenRandomString("ЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕ", 100);
- //////////////////////////////////////
- Stopwatch first_timer = new Stopwatch();
- first_timer.Start();
- RabinKarp(ran1, ran2);
- first_timer.Stop();
- Console.WriteLine("Время выполнения для первой подстроки в мс: " + first_timer.ElapsedMilliseconds + " В тактах: " + first_timer.ElapsedTicks);
- //////////////////////////////////////
- Stopwatch second_timer = new Stopwatch();
- second_timer.Start();
- RabinKarp1(ran1, ran3);
- second_timer.Stop();
- Console.WriteLine("Время выполнения для второй подстроки в мс: " + second_timer.ElapsedMilliseconds + " В тактах: " + second_timer.ElapsedTicks);
- //////////////////////////////////////
- }
- }
- }
Add Comment
Please, Sign In to add comment