namespace Algorithms.Strings
{
    /// <summary>Implementation Z-block substring search.
    /// </summary>
    public static class ZblockSubstringSearch
    {
        /// <summary>
        ///     This algorithm finds all occurrences of a pattern in a text in linear time - O(m+n).
        /// </summary>
        public static int FindSubstring(string pattern, string text)
        {
            var concatStr = $"{pattern}${text}";
            var patternLength = pattern.Length;
            var n = concatStr.Length;
            var zArray = new int[n];

            var left = 0;
            var right = 0;

            for(var i = 1; i < n; i++)
            {
                if(i > right)
                {
                    left = i;
                    right = ComputeNewRightValue(concatStr, n, left, i);

                    zArray[i] = right - left;
                    right--;
                }
                else
                {
                    var k = i - left;
                    if (zArray[k] < (right - i + 1))
                    {
                        zArray[i] = zArray[k];
                    }
                    else
                    {
                        left = i;
                        right = ComputeNewRightValue(concatStr, n, left, right);
                        zArray[i] = right - left;
                        right--;
                    }
                }
            }

            var found = 0;
            foreach(var z_value in zArray)
            {
                if(z_value == patternLength)
                {
                    found++;
                }
            }

            return found;
        }

        private static int ComputeNewRightValue(string concatStr, int n, int left, int right)
        {
            while (right < n && concatStr[right - left].Equals(concatStr[right]))
            {
                right++;
            }

            return right;
        }
    }
}