using System;

using System.Collections.Generic;

​

/*

Write a program and take these values to find all of the different patterns in "input" of length 

"patternLength" and output all of the patterns that occur more than once and the number of times they occur.

​

For example, when searching the string "zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=", with a specified

pattern length of 3, the method should return the pattern "abx” with an occurrence value of two,

and “zf3” with an occurrence value of three.

​

​

Validations:

1. patternLength must >= 0

2. input string can only be non null

3. input.Length >= patternLength

4. patternLength must be a positive integer

5. Patterns do not overlap, that is, if another pattern is part of a pattern that matches it is no longer considered.

6. there must be greater than one pattern in input

*/

public class TotalPatternCount

{

    public string Pattern

    { get; set;

    }

    public string Overlap

    { get; set;

    }

    public int Counter

    { get; set;

    }

​

}

​

public class PatternSearcher

{

    /* 

    Returns the portion of the original input string that overlaps with the pattern

    found at index or the remainder of the original input if it is not long enough.

    ex. zf3kabx, index = 0, patternLength = 3: return f3ka

    */

    private static string FindOverlap(string input, int index, int patternLength)

    {

        // patternLength * 2 -2 is because the last possible overlap is the last character in the original pattern + patternLength but since we are excluding the first character we subtract 1 more to get that value.

        var newPatternLength = patternLength * 2 - 2;

        var len = Math.Min(newPatternLength, input.Length - (index + 1));

        return input.Substring(index + 1, len);

    }

​

    /*

    Decreases all overlapping patterns associated with the specified pattern by 1

    */

    private static void DecreaseOverlaps(Dictionary<string, TotalPatternCount> patterns, string pattern, int patternLength)

    {

        var input = patterns[pattern].Overlap;

        int i = 0; 

        while (i + patternLength <= input.Length)

        {

            string overlapFound = input.Substring(i, patternLength);

            if (patterns.ContainsKey(overlapFound))

            {

                patterns[overlapFound].Counter -= 1;

                //decrease count by 1 if overlap is found

                if (patterns[overlapFound].Counter <= 0 && pattern != overlapFound)

                { // remove overlap if it is not a pattern

                    patterns.Remove(overlapFound);

                }

            }

            i++;

        }

    }

​

    /*

    returns a dictionary containg patterns of a specified length and the number of times they appear

    in the input string.

     */

    public static Dictionary<string, TotalPatternCount> CountPatterns(string input, int patternLength)

    {

        if (patternLength <= 0)

        {

            throw new ArgumentOutOfRangeException("patternLength expected >= 0 but found {patternLength} instead.");

        }

​

        if (input == null || input.Length == 0)

        {

            throw new ArgumentException("Please enter non empty string as input.");

        }

​

        var patterns = new Dictionary<string, TotalPatternCount>();

        int i = 0;

        while (i + patternLength <= input.Length)

        {

            string pattern = input.Substring(i, patternLength);

            if (patterns.ContainsKey(pattern))

            {

                patterns[pattern].Counter = patterns[pattern].Counter + 1;

                DecreaseOverlaps(patterns, pattern, patternLength);

                patterns[pattern].Overlap = FindOverlap(input, i, patternLength);

            }

            else

            {

                var overlap = FindOverlap(input, i, patternLength);

                patterns[pattern] = new TotalPatternCount{Pattern = pattern, Counter = 1, Overlap = overlap};

            }

            i++;

        }

​

        return patterns;

    }

​

    /* Retuns a list of PatternCounts that have at least the minimum count specified. */

    public static List<TotalPatternCount> FilterAboveCount(Dictionary<string, TotalPatternCount> patterns)

    {

        var resultsList = new List<TotalPatternCount>();

        foreach (var item in patterns)

        {

            if (item.Value.Counter >= 2) //minimum count

            {

                resultsList.Add(item.Value);

            }

        }

​

        return resultsList;

    }

​

    public static void Main()

    {

        Console.WriteLine("Enter string:");

        var searchString = Console.ReadLine();

        Console.WriteLine("Enter Pattern Length:");

        int patternLength;

        if (int.TryParse(Console.ReadLine(), out patternLength))

        {

            var results = FilterAboveCount(CountPatterns(searchString, patternLength));

            Console.WriteLine("Found the following patterns greater than 1 match:");

            foreach (var item in results)

            {

                //Console.WriteLine("{item.Pattern} = {item.Counter}");

                Console.WriteLine(item.Pattern + " has occurance of " + item.Counter);

            }

        }

        else

        {

            Console.WriteLine("Please input a valid number for patternLength");

        }

​

        Console.WriteLine("Press any key try again");

        Console.ReadLine();

        Console.WriteLine("__________________________");

        Main();

    }

}