Практика 12 № 11

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

namespace Hash
{
    class Program
    {
        //Метод для получения хеш-значения для подстроки с индексами L и R
        static long GetHash(long[] h, int L, int R)
        {
            if (L > 0) return h[R] - h[L - 1];
            return h[R];
        }
        //Метод для получения хеш-значения для «перевернутой» подстроки с индексами L и R
        static long GetHashRevers(long[] h_r, int L, int R)
        {
            if (R < h_r.Length - 1) return h_r[L] - h_r[R + 1];
            return h_r[L];
        }
        //Метод возвращает true, если строка палиндром, иначе false
        static bool IsPalindrome(long[] h, long[] h_r, long[] pwp, int L, int R)
        {
            return GetHash(h, L, R) * pwp[h.Length - R - 1] == GetHashRevers(h_r, L, R) * pwp[L];
        }
        //Метод для вывода на экран всех палиндром строки S
        static void Print(int[] oddCount, int[] evenCount, string s)
        {
            Console.WriteLine("Палиндромы:");
            for (int i = 0; i < oddCount.Length; ++i) //вывод палиндромов нечетной длины
            {
                if (oddCount[i] > 1) //1
                    Console.WriteLine(s.Substring(i - oddCount[i] + 1, oddCount[i] * 2 - 1));
            }
            for (int i = 0; i < evenCount.Length; ++i) //вывод палиндромов четной длины
            {
                if (evenCount[i] * 2 - i + evenCount[i] > 0)
                    Console.WriteLine(s.Substring(i - evenCount[i], evenCount[i] * 2));
            }
        }
        static string generator(int length)
        {
            Random rnd = new Random();
            char cur;
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < length; i++)
            {
                cur = (char)((int)'0' + rnd.Next(0, 9));
                result.Append(cur);
            }
            return result.ToString();
        }
        static void Main(string[] args) //основной метод
        {
            Console.Write("S= ");

            string s = generator(1000);
            Console.WriteLine(s);
            int n = s.Length; //2
            const long P = 37;
            //вычисляем массив степеней
            long[] pwp = new long[n];
            pwp[0] = 1;
            for (int i = 1; i < n; i++)
            {
                pwp[i] = pwp[i - 1] * P;

            }
            //вычисляем массив хэш-значений для всех префиксов строки S и
            //перевернутой строки
            long[] h = new long[n];
            long[] h_r = new long[n];
            for (int i = 0; i < n; i++)
            {
                h[i] = (s[i] - 'a' + 1) * pwp[i];
                h_r[n - 1 - i] = (s[n - 1 - i] - 'a' + 1) * pwp[i];
                if (i > 0)
                {
                    h[i] += h[i - 1];
                    h_r[n - 1 - i] += h_r[n - i];
                }
            }
            //поиск палиндромов нечетной длины
            int[] oddCount = new int[n];
            for (int i = 0; i < n; i++)
            {
                int left = 1, right = Math.Min(i + 1, n - i);
                while (left <= right)
                {
                    int middle = (left + right) / 2;
                    if (IsPalindrome(h, h_r, pwp, i - middle + 1, i + middle - 1))
                    {
                        oddCount[i] = middle;
                        left = middle + 1;
                    }
                    else
                    {
                        right = middle - 1;
                    }
                }
            }
            //поиск палиндромов четной длины
            int[] evenCount = new int[n];
            for (int i = 0; i < n; i++)
            {
                int left = 1, right = Math.Min(i, n - i);
                while (left <= right)
                {
                    int middle = (left + right) / 2;
                    if (IsPalindrome(h, h_r, pwp, i - middle, i + middle - 1))
                    {
                        evenCount[i] = middle;
                        left = middle + 1;
                    }
                    else
                    {
                        right = middle - 1;
                    }
                }
            }
            Print(oddCount, evenCount, s); //вывод на экран всех палиндромов
        }
    }
}