Алгоритм Рыбина-Карпа

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Строка (текст): ");
            string t = Console.ReadLine();

            Console.Write("Подстрока: ");
            string s = Console.ReadLine();

            const long p = 37;

            // =============================================================================
            // ШАГ 1: Подсчет значений степеней числа p: p^0, p^1, p^2, ..., p^{t.length}
            // =============================================================================

            long[] degreeP = new long[t.Length]; degreeP[0] = 1;

            for (int i = 1; i < t.Length; ++i)
                degreeP[i] = degreeP[i - 1] * p;

            // =============================================================================
            // ШАГ 2: Подсчет хэш-значений для всех ПРЕФИКСОВ строки t
            // =============================================================================

            long[] hashT = new long[t.Length]; hashT[0] = (t[0] - 'a' + 1);

            for (int i = 1; i < t.Length; ++i)
            {
                hashT[i] = (t[i] - 'a' + 1) * degreeP[i];
                hashT[i] += hashT[i - 1];
            }

            // =============================================================================
            // ШАГ 3: Подсчет хэш-значений для ПОДСТРОКИ s
            // =============================================================================

            long hashS = 0;

            for (int i = 0; i < s.Length; ++i)
                hashS += (s[i] - 'a' + 1) * degreeP[i];

            // =============================================================================
            // ШАГ 4: Поиск подстроки за счет сравнения хэш-значений подстрок
            // =============================================================================

            for (int i = 0; i + s.Length - 1 < t.Length; i++)
            {
                // Находим хэш-значение подстроки t[i..i + s.length - 1]
                long cur_hash = hashT[i + s.Length - 1];

                if (i > 0) cur_hash -= hashT[i - 1];

                // Приводим хэш-значения двух подстрок к одной степени
                if (cur_hash == hashS * degreeP[i]) // если хеш-значения равны, то и подстроки равны
                {
                    Console.Write("{0} ", i); // выводим позицию i, с которой начинается повторение
                }
            }
        }
    }
}