27

bacons schifer.cs

using System;
using System.Collections.Generic;

namespace BaconsChipher  
{
    class EntryPoint
    {
        //public static int Module = 1000000009;
        //public static int Module = 1073676287;
        //public static int Module = 2147483647;
        public const ulong m = 87178291199;
        public const ulong p = 263; 

        public static int ToCode(char c)
        {
            return c - 'a' + 1;
        }

        public static void Main()
        {
            var s = Console.ReadLine();

            var count = 1;
            var n = s.Length;

            var prefixHashes = new ulong[n];
            var pows = new ulong[n];

            prefixHashes[0] = (ulong)ToCode(s[0]);
            pows[0] = 1;

            for (var i = 1; i < n; i++)
            {
                prefixHashes[i] = ((prefixHashes[i - 1] * p) % m + (ulong)ToCode(s[i])) % m;
                pows[i] = (pows[i - 1] * p) % m;
            }

            var set = new HashSet<ulong>();

            for (var l = 1; l < n; l++)
            {
                set.Clear();

                var hash = prefixHashes[l - 1];

                //Console.WriteLine(s.Substring(0, l) + " " + hash);
                set.Add(hash);

                for (var i = 1; i < n - l + 1; i++)
                {
                    var t = ((ulong)ToCode(s[i - 1]) * pows[l - 1]) % m;
                    var t1 = (((hash - t + m) % m) * p) % m;

                    hash = (t1 + (ulong)ToCode(s[i + l - 1])) % m;


                    //if (!set.Contains(hash))
                    //{
                        //Console.WriteLine(s.Substring(i, l) + " " + hash);
                        set.Add(hash);
                    //}
                }

                count += set.Count;
            }

            Console.WriteLine(count);
        }
    }
}