prac 12

// Исходная строка – 10000 символов из романа «Война и мир», искомая строка: а) «князь» б) «императрица»

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            using (StreamReader input = new StreamReader("C:/Users/gorbachevap/Desktop/practice/input_12.txt", Encoding.GetEncoding(1251)))
            {
                string text = input.ReadToEnd();
                Console.WriteLine("Введите искомое слово: ");
                string s = Console.ReadLine();
                const long P = 37;
                long[] arr = new long[text.Length];
                arr[0] = 1;
                for (int i = 1; i < text.Length; i++)
                {
                    arr[i] = arr[i - 1] * P;
                }
                long[] h_arr = new long[text.Length];
                for (int i = 0; i < text.Length; i++)
                {
                    h_arr[i] = (text[i] - 'a' + 1) * arr[i]; //1
                    if (i > 0)
                        h_arr[i] += h_arr[i - 1];
                }
                long h_s = 0;
                for (int i = 0; i < s.Length; i++)
                {
                    h_s += (s[i] - 'a' + 1) * arr[i];
                }//проводим поиск по хеш-значениям

                using (StreamWriter output = new StreamWriter("C:/Users/gorbachevap/Desktop/practice/output_12.txt", true))
                {
                    for (int i = 0; i + s.Length - 1 < text.Length; i++)
                    {
                        // находим хэш-значение подстроки T начиная с позиции i длиною s.Length
                        long cur_h = h_arr[i + s.Length - 1];
                        bool flag = false;
                        if (i > 0)
                        {
                            cur_h -= h_arr[i - 1];
                        }//приводим хэш-значения двух подстрок к одной степени
                        if (cur_h == h_s * arr[i]) // если хеш-значения равны, то и подстроки равны
                        {
                            flag = true;
                            output.WriteLine("Слово {0} найдено на {1}", s, i); // выводим позицию i, с которой начинается повторение
                        }
                        if (!flag)
                            output.WriteLine("Слов не найдено");
                    }
                }
            }

        }
    }
}