12 (S)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using System.IO;


namespace ConsoleApp1
{
    class Program
    {

        static string generator(int n)
        {
            Random rand = new Random();
            char cur;
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < n; i++)
            {
                cur = (char)('a' + rand.Next(0, 9));
                result.Append(cur);
            }
            return result.ToString();
        }
        static void Main(string[] args)
        {
            string t = generator(10000);
            string s = generator(3);
            using (StreamWriter output = new StreamWriter("C:/Users/karpenkoos/desktop/output.txt"))
            {
                output.WriteLine($"T = {t}");
                output.WriteLine($"S = {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];
                }
                //проводим поиск по хеш-значениям
                output.WriteLine("индексы вхождений:");
                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]) // если хеш-значения равны, то и подстроки равны
                    {
                        output.WriteLine("{0} ", i); // выводим позицию i, с которой начинается повторение
                    }
                }
            }
        }
    }
}