using System;

using System.Collections.Generic; 

public class Program

{

    public static void Main()

    {

        string str = "zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=";

        //string str = "ababa";

        // print results

        PatternOccurenceFinder finder = new PatternOccurenceFinderImp1();

        List<Output> patterns = finder.findPatternsOfLength(str, 3);

        foreach(Output pattern in patterns) {

            Console.WriteLine("Pattern: {0}\t Occurence: {1}\n",

                              pattern.getPattern(), pattern.getOccurences());

        }

    }

    /***

    * This interface has a method which finds all patterns of specified length with more than one 

    * occurences and return the outputs as a list

    */

    public interface PatternOccurenceFinder {

        List<Output> findPatternsOfLength(string str, int length);

    }

    /** Implementation 1

     *  This implementation allows patterns overlapping each other, 

     *  i.e, the pattern "aba" in "ababa" has an occurence of 2

     *

     *  It processes each substring of a string and keep track of

     *  the occurences using a dictionary.

     */

    public class PatternOccurenceFinderImp1 : PatternOccurenceFinder {

        public List<Output> findPatternsOfLength(string str, int length)

        {

            Dictionary<string, int> patternOccurences = new Dictionary<string, int>();

​

            for (int i = 0; i <= str.Length - length; i++) {

                string subStr = str.Substring(i, length);

                if (patternOccurences.ContainsKey(subStr)) {

                    patternOccurences[subStr]++;

                }

                else {

                    patternOccurences.Add(subStr, 1);

                }

            }

​

            List<Output> patterns = new List<Output>();

            foreach(KeyValuePair<string, int> patternOccurence in patternOccurences) 

            { 

                if (patternOccurence.Value > 1) {

                    Output pattern = new Output(patternOccurence.Key, patternOccurence.Value);

                    patterns.Add(pattern);

                }

            }

​

            return patterns;

        }

    }

    /** Implementation 2

     *  This implementation does not allow patterns overlapping each other, 

     *  i.e, the pattern "aba" in "ababa" only occured once

     *

     *  Just like in implementation 1, 

     *  It processes each substring of a string and find its non-overlapping 

     *  occurence and keep track of it using a dictionary.

     */

    public class PatternOccurenceFinderImp2 : PatternOccurenceFinder {

        public List<Output> findPatternsOfLength(string str, int length)

        {

            Dictionary<string, int> patternOccurences = new Dictionary<string, int>();

            for (int i = 0; i <= str.Length - length; i++) {

                string subStr = str.Substring(i, length);

                if (!patternOccurences.ContainsKey(subStr)) {

                    int occurence = 1 + findPatternOccurence(subStr, str.Substring(length+i));

                    patternOccurences.Add(subStr, occurence);

                }

            }

​

            List<Output> patterns = new List<Output>();

            foreach(KeyValuePair<string, int> patternOccurence in patternOccurences) 

            { 

                if (patternOccurence.Value > 1) {

                    Output pattern = new Output(patternOccurence.Key, patternOccurence.Value);

                    patterns.Add(pattern);

                }

            }

​

            return patterns;

        }

        private int findPatternOccurence(string pattern, string str) {

            for (int i = 0; i <= str.Length - pattern.Length; i++) {

                string subStr = str.Substring(i, pattern.Length);

                if (subStr.Equals(pattern)) {

                    return 1 + findPatternOccurence(pattern, str.Substring(i + pattern.Length));

                }

            }

            return 0;

        }

    }

    /* class for output */

    public class Output {

        private string pattern;

        private int occurence;

        public Output(String pattern, int occurence) {

            this.pattern = pattern;

            this.occurence = occurence;

        }

        public string getPattern() {

            return pattern;

        }

        public int getOccurences() {

            return occurence;

        }

    }

}