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)
        {
            StreamReader input = new StreamReader("e:/practice/input.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];
            }//проводим поиск по хеш-значениям
            StreamWriter output = new StreamWriter("e:/practice/output.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];
                if (i > 0)
                {
                    cur_h -= h_arr[i -1];
                }//приводим хэш-значения двух подстрок к одной степени
                if (cur_h == h_s * arr[i]) // если хеш-значения равны, то и подстроки равны
                {
                    output.WriteLine("Слово {0} найдено на {1}", s, i); // выводим позицию i, с которой начинается повторение
                }
            }

    }
}
}