Ochkasty_Dino

Practicum12-5 переделать

Nov 18th, 2019
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 5.57 KB | None | 0 0
  1. using System;
  2. using System.Text;
  3. using System.Diagnostics;
  4. namespace ConsoleApp5
  5. {
  6.     class Program
  7.     {
  8.         public static string GenRandomString(string Alphabet, int Length)
  9.         {
  10.             Random rnd = new Random();
  11.             StringBuilder sb = new StringBuilder(Length - 1);
  12.             int Position = 0;
  13.             for (int i = 0; i < Length; i++)
  14.             {
  15.                 Position = rnd.Next(0, Alphabet.Length - 1);
  16.                 sb.Append(Alphabet[Position]);
  17.             }
  18.             return sb.ToString();
  19.         }
  20.         public static void RabinKarp1(string t, string s)
  21.         {
  22.             const long P = 37;
  23.             //вычисляем массив степеней P
  24.             long[] pwp = new long[t.Length];
  25.             pwp[0] = 1;
  26.             for (int i = 1; i < t.Length; i++)
  27.             {
  28.                 pwp[i] = pwp[i - 1] * P;
  29.             }
  30.             //вычисляем массив хэш-значение для всех префиксов строки T
  31.             long[] h = new long[t.Length];
  32.             for (int i = 0; i < t.Length; i++)
  33.             {
  34.                 h[i] = (t[i] - 'a' + 1) * pwp[i]; //1
  35.                 if (i > 0)
  36.                     h[i] += h[i - 1];
  37.             }
  38.             // вычисляем хэш-значение для подстроки S
  39.             long h_s = 0;
  40.             for (int i = 0; i < s.Length; i++)
  41.             {
  42.                 h_s += (s[i] - 'a' + 1) * pwp[i];
  43.             }
  44.             //проводим поиск по хеш-значениям
  45.             for (int i = 0; i + s.Length - 1 < t.Length; i++)
  46.             {
  47.                 // находим хэш-значение подстроки T начиная с позиции i длиною s.Length
  48.                 long cur_h = h[i + s.Length - 1];
  49.                 if (i > 0)
  50.                 {
  51.                     cur_h -= h[i - 1];
  52.                 }
  53.                 //приводим хэш-значения двух подстрок к одной степени
  54.                 if (cur_h == h_s * pwp[i]) // если хеш-значения равны, то и подстроки равны
  55.                 {
  56.                     Console.Write("{0} ", i); // выводим позицию i, с которой начинается повторение
  57.                 }
  58.             }
  59.         }
  60.         public static void RabinKarp(string t, string s)
  61.         {
  62.             const long P = 37;
  63.             //вычисляем массив степеней P
  64.             long[] pwp = new long[t.Length];
  65.             pwp[0] = 1;
  66.             for (int i = 1; i < t.Length; i++)
  67.             {
  68.                 pwp[i] = pwp[i - 1] * P;
  69.             }
  70.             //вычисляем массив хэш-значение для всех префиксов строки T
  71.             long[] h = new long[t.Length];
  72.             for (int i = 0; i < t.Length; i++)
  73.             {
  74.                 h[i] = (t[i] - 'a' + 1) * pwp[i]; //1
  75.                 if (i > 0)
  76.                     h[i] += h[i - 1];
  77.             }
  78.             // вычисляем хэш-значение для подстроки S
  79.             long h_s = 0;
  80.             for (int i = 0; i < s.Length; i++)
  81.             {
  82.                 h_s += (s[i] - 'a' + 1) * pwp[i];
  83.             }
  84.             //проводим поиск по хеш-значениям
  85.             for (int i = 0; i + s.Length - 1 < t.Length; i++)
  86.             {
  87.                 // находим хэш-значение подстроки T начиная с позиции i длиною s.Length
  88.                 long cur_h = h[i + s.Length - 1];
  89.                 if (i > 0)
  90.                 {
  91.                     cur_h -= h[i - 1];
  92.                 }
  93.                 //приводим хэш-значения двух подстрок к одной степени
  94.                 if (cur_h == h_s * pwp[i]) // если хеш-значения равны, то и подстроки равны
  95.                 {
  96.                     Console.Write("{0} ", i); // выводим позицию i, с которой начинается повторение
  97.                 }
  98.             }
  99.         }
  100.         static void Main(string[] args)
  101.         {
  102.             string ran1 = GenRandomString("ПРИТОНПРИТОНПРИТОНПРИТОНПРИТОНПРИТОНПРИТОНПРИТОН", 10000);
  103.             string ran2 = GenRandomString("ПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕПОЛОЖЕНИЕ", 3);
  104.             string ran3 = GenRandomString("ЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕЖИВОТНЫЕ", 100);
  105.             //////////////////////////////////////
  106.             Stopwatch first_timer = new Stopwatch();
  107.             first_timer.Start();
  108.             RabinKarp(ran1, ran2);
  109.             first_timer.Stop();
  110.             Console.WriteLine("Время выполнения для первой подстроки в мс: " + first_timer.ElapsedMilliseconds + " В тактах: " + first_timer.ElapsedTicks);
  111.             //////////////////////////////////////
  112.             Stopwatch second_timer = new Stopwatch();
  113.             second_timer.Start();
  114.             RabinKarp1(ran1, ran3);
  115.             second_timer.Stop();
  116.             Console.WriteLine("Время выполнения для второй подстроки в мс: " + second_timer.ElapsedMilliseconds + " В тактах: " + second_timer.ElapsedTicks);
  117.             //////////////////////////////////////
  118.         }
  119.     }
  120. }
Add Comment
Please, Sign In to add comment