Advertisement
Sephinroth

prac 12

Dec 9th, 2019
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.83 KB | None | 0 0
  1. // Исходная строка – 10000 символов из романа «Война и мир», искомая строка: а) «князь» б) «императрица»
  2.  
  3. using System;
  4. using System.Collections.Generic;
  5. using System.Linq;
  6. using System.Text;
  7. using System.IO;
  8.  
  9. namespace ConsoleApplication2
  10. {
  11.     class Program
  12.     {
  13.         static void Main(string[] args)
  14.         {
  15.             using (StreamReader input = new StreamReader("C:/Users/gorbachevap/Desktop/practice/input_12.txt", Encoding.GetEncoding(1251)))
  16.             {
  17.                 string text = input.ReadToEnd();
  18.                 Console.WriteLine("Введите искомое слово: ");
  19.                 string s = Console.ReadLine();
  20.                 const long P = 37;
  21.                 long[] arr = new long[text.Length];
  22.                 arr[0] = 1;
  23.                 for (int i = 1; i < text.Length; i++)
  24.                 {
  25.                     arr[i] = arr[i - 1] * P;
  26.                 }
  27.                 long[] h_arr = new long[text.Length];
  28.                 for (int i = 0; i < text.Length; i++)
  29.                 {
  30.                     h_arr[i] = (text[i] - 'a' + 1) * arr[i]; //1
  31.                     if (i > 0)
  32.                         h_arr[i] += h_arr[i - 1];
  33.                 }
  34.                 long h_s = 0;
  35.                 for (int i = 0; i < s.Length; i++)
  36.                 {
  37.                     h_s += (s[i] - 'a' + 1) * arr[i];
  38.                 }//проводим поиск по хеш-значениям
  39.                
  40.                 using (StreamWriter output = new StreamWriter("C:/Users/gorbachevap/Desktop/practice/output_12.txt", true))
  41.                 {
  42.                     for (int i = 0; i + s.Length - 1 < text.Length; i++)
  43.                     {
  44.                         // находим хэш-значение подстроки T начиная с позиции i длиною s.Length
  45.                         long cur_h = h_arr[i + s.Length - 1];
  46.                         bool flag = false;
  47.                         if (i > 0)
  48.                         {
  49.                             cur_h -= h_arr[i - 1];
  50.                         }//приводим хэш-значения двух подстрок к одной степени
  51.                         if (cur_h == h_s * arr[i]) // если хеш-значения равны, то и подстроки равны
  52.                         {
  53.                             flag = true;
  54.                             output.WriteLine("Слово {0} найдено на {1}", s, i); // выводим позицию i, с которой начинается повторение
  55.                         }
  56.                         if (!flag)
  57.                             output.WriteLine("Слов не найдено");
  58.                     }
  59.                 }
  60.             }
  61.  
  62.         }
  63.     }
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement