using System;
using System.Collections.Generic;

namespace Substring
{
    public class RabinKarpAlgorithm : ISubstringSearch
    {
        private readonly int _baseOfTheNumeralSystem;
        private readonly int _primeNumber;

        public RabinKarpAlgorithm(int baseOfTheNumeralSystem = char.MaxValue, int primeNumber = 115249)
        {
            _baseOfTheNumeralSystem = baseOfTheNumeralSystem;
            _primeNumber = primeNumber;
        }

        public List<int> IndexesOf(string input, string pattern)
        {
            List<int> indexesList = new List<int>();
            int inputLength = input.Length;
            int patternLength = pattern.Length;
            int maxBase = GetMaxBase(patternLength, _primeNumber, _baseOfTheNumeralSystem);
            int patternHash = GetHashOfString(pattern, _primeNumber, _baseOfTheNumeralSystem);
            int substringHash =
                GetHashOfString(input.Substring(0, patternLength), _primeNumber, _baseOfTheNumeralSystem);

            for (int i = 0; i <= inputLength - patternLength; i++)
            {

                if (patternHash == substringHash)
                {
                    bool success = true;
                    for (int j = 0; j < patternLength; j++)
                    {
                        if (input[i + j] != pattern[j])
                        {
                            success = false;
                            break;
                        }
                    }
                    if (success)
                        indexesList.Add(i);
                }
                if (i != inputLength - patternLength)
                    substringHash =
                        (_baseOfTheNumeralSystem * (substringHash - input[i] * maxBase) +
                        input[i + patternLength]) % _primeNumber;
                if (substringHash < 0) substringHash += _primeNumber;
            }
            return indexesList;
        }
        private int GetHashOfString(string s, int q, int b)
        {
            int result = 0;
            int length = s.Length;

            for (int i = 0; i < length; i++)
                result = (b * result + s[i]) % q;
            return result;
        }
        private int GetMaxBase(int length, int q, int b)
        {
            int result = 1;
            for (int i = 0; i < length - 1; i++)
                result = (result * b) % q;
            return result;
        }
    }
}