Mohit Rupani | C# Online Compiler

Mohit Rupani by Anonymous

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

namespace FrozenMountain
{
    public class Program
    {
        /* 
         * Name: 
         *      ValidateInputParameters
         * Definition: 
         *      This function validates the input parameters - input string and pattern length.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.    
         * Output Parameters:      
         *      1) errMsg: validation error, if any.
         * Return Type:
         *      bool: True/False is returned along with the validation error message.
         */
        static bool ValidateInputParameters(string inputStr, string pattern, ref string errMsg)
        {
            int pLength;
            if (inputStr == null || inputStr.Length < 2)
            {
                errMsg = " Error: Invalid Input Parameters. The input string is empty or invalid.";
                return false;
            }           

            if (pattern == null || !(int.TryParse(pattern, out pLength))) {
                errMsg = " Error: Invalid Input Parameters. The pattern length is empty or invalid.";
                return false;
            }

            if (pLength < 1)
            {
                errMsg = " Error: Invalid Input Parameters. The pattern length has to be atleast 1.";
                return false;
            }

            if (inputStr.Length <= pLength)
            {
                errMsg = " Error: Invalid Input Parameters. The length of the pattern should be less than the length of the input string.";
                return false;
            }

            errMsg = string.Empty;
            return true;
        }

        /* 
         * Name: 
         *      FindPattern_BruteForce
         * Definition: 
         *      This function uses the brute force method of finding the pattern string
         *      by simply using nested 'for' loops to find the pattern. Once the pattern is found, 
         *      the pattern is added to a Dictionary Object called as 'result' or 
         *      its count is incremented by one if it already exists in the dictionary object due to the previous find.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.         
         * Output Parameters:      
         *      1) patternList: this contains the list of patterns found in the input string along with their count, 
         *         in a (key,value) pair.
         * Return Type:
         *      Void: No return type since the 'patternList' is a reference-type object.
         */
        static void FindPattern_BruteForce(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);

                string searchString; // this is the pattern the needs to be searched in the input string
                string patternString; // this is the pattern to compare for equality

                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    searchString = inputStr.Substring(i, pLength);

                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        int patternCount = 1;
                        for (int j = i + 1; j <= (inputStr.Length - pLength); j++)
                        {
                            patternString = inputStr.Substring(j, pLength);
                            if (searchString == patternString)
                            {
                                patternCount++;
                            }
                        }

                        if (patternCount > 1)
                        {
                            patternList.Add(searchString, patternCount); // its a new pattern
                        }
                    }
                }
            }

            catch (Exception)
            {
                throw;
            }
        }
   
        /* 
         * Name: 
         *      FindPattern_UsingRecursion
         * Definition: 
         *      This function iterates the input string and  calls a recursive function to 
         *      find the count of a pattern string. Once the pattern is found, the pattern 
         *      and its count is added to the 'patternList' as a (Key, Value) pair.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.
         * Output Parameters:      
         *      1) patternList: this contains the list of patterns found in the input string along with their count, 
         *         in a (key,value) pair.
         * Return Type:
         *      Void: No return type since the 'patternList' is a reference-type object.
         */
        static void FindPattern_UsingRecursion(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);

                string searchString; // this is the pattern the needs to be searched in the input string

                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    searchString = inputStr.Substring(i, pLength);

                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        int patternCount = 1;
                        GetPatternCount(inputStr.Substring(i + 1), searchString, ref patternCount);
                        if (patternCount > 1)
                        {
                            patternList.Add(searchString, patternCount); // its a new pattern
                        }
                    }
                }
            }
            catch (Exception)
            {
                throw;
            }
        }

        /* 
        * Name: 
        *      GetPatternCount
        * Definition: 
        *      This function calculates the number of times a pattern occures in an input string recursively. 
        * Input Parameters:
        *      1) inputStr: this is the input string to look for the pattern.
        *      2) patternStr: this is the pattern string.
        * Output Parameters:      
        *      1) patternCount: number of times the pattern string occurs in the input.
        * Return Type:
        *      Void: No return type since the 'patternCount' argument is passed by reference.
        */
        static void GetPatternCount(string inputStr, string patternStr, ref int patternCount)
        {
            if (inputStr == patternStr)
            {
                patternCount++;
                return;
            }
            else
            {
                if (inputStr.IndexOf(patternStr) != -1)
                {
                    patternCount++;
                    GetPatternCount(inputStr.Substring(inputStr.IndexOf(patternStr) + 1), patternStr, ref patternCount);
                }
                else
                {
                    return;
                }
            }
        }

        /* 
         * Name: 
         *      FindPattern_UsingRegex
         * Definition: 
         *      This function iterates the input string and  uses the 'Regex' C# class to 
         *      find the count of a pattern string. Once the pattern is found, the pattern 
         *      and its count is added to the 'patternList' as a (Key, Value) pair. 
         *      Since the pattern string can contain special/meta-characters of a regular expression,
         *      Regex.Escape() function is used to treat them as literals.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.
         * Output Paramters:      
         *      1) patternList: this contains the list of patterns found in the input string along with their count, 
         *         in a (key,value) pair.
         * Return Type:
         *      Void: No return type since the 'patternList' is a reference-type object.
         */
        static void FindPattern_UsingRegex(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);

                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    string searchString = inputStr.Substring(i, pLength); // this is the pattern the needs to be searched in the input string                

                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        string regexExpr = inputStr;
                        var patternMatch = Regex.Match(regexExpr, Regex.Escape(searchString));
                        int patternCount = 0;

                        while (patternMatch.Success)
                        {
                            patternCount++;
                            regexExpr = regexExpr.Substring(patternMatch.Index + 1);
                            patternMatch = Regex.Match(regexExpr, Regex.Escape(searchString));
                        }

                        if (patternCount > 1)
                        {
                            patternList.Add(searchString, patternCount);
                        }
                    }
                }
            }

            catch (Exception)
            {
                throw;
            }
        }

        /* 
        * Name: 
        *      FindPattern_UsingBayerMooreAlgo
        * Definition: 
        *      This function iterates the input string and  uses the Bayer-Moore Algorithm 
        *      (with bad match table approach) to find the count of a pattern string. 
        * Input Parameters:
        *      1) inputStr: this is the input string to look for the pattern.
        *      2) pLength: this is the length of the pattern for conducting the search in the input string.
        * Output Paramters:      
        *      1) patternList: this contains the list of patterns found in the input string along with their count, 
        *         in a (key,value) pair.
        * Return Type:
        *      Void: No return type since the 'patternList' is a reference-type object.
        */
        static void FindPattern_UsingBayerMooreAlgo(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);
                int shiftPos;
                Dictionary<char, int> badMatchTable = new Dictionary<char, int>();

                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    string searchString = inputStr.Substring(i, pLength); // this is the pattern the needs to be searched in the input string                               
                    badMatchTable.Clear();

                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        //creating a bad match table
                        for (int j = 0; j < searchString.Length; j++)
                        {
                            int value;
                            shiftPos = Math.Max(1, (pLength - j - 1));
                            if (badMatchTable.TryGetValue(searchString[j], out value))
                            {
                                badMatchTable[searchString[j]] = shiftPos;
                            }
                            else
                            {
                                badMatchTable.Add(searchString[j], shiftPos);
                            }
                        }
                        BayerMooreSearch(searchString, inputStr.Substring(i + 1), badMatchTable, patternList);
                    }
                }
            }

            catch (Exception)
            {
                throw;
            }
        }

        /* 
        * Name: 
        *      BayerMooreSearch
        * Definition: 
        *      This function uses the Bayer-Moore Algorithm (with bad match table approach) to find the count of a pattern string. 
        *      Once the pattern is found, the pattern and its count is added to the 'patternList' as a (Key, Value) pair. 
        * Input Parameters:
        *      1) ipString: this is the input string to look for the pattern.
        *      2) pString: this is the pattern string.
        *      3) bmTable: this is the bad-match table list to make the appropriate position shifts during the search.
        * Output Paramters:      
        *      1) pList: this contains the list of patterns found in the input string along with their count, 
        *         in a (key,value) pair.
        * Return Type:
        *      Void: No return type since the 'pList' is a reference-type object.
        */
        static void BayerMooreSearch(string pString, string ipString, IDictionary<char,int> bmTable, IDictionary<string, int> pList)
        {
            int pLength = pString.Length;            
            int patternIndex = pLength - 1;
            int inputIndex = pLength - 1;
            int startIndex = inputIndex;
            bool isMatch = true;

            while (inputIndex < ipString.Length)
            {
                if (pString[patternIndex] == ipString[inputIndex])
                {
                    while(patternIndex >= 0 && isMatch)
                    {                        
                        if (pString[patternIndex] == ipString[inputIndex])
                        {
                            patternIndex--;
                            inputIndex--;
                        }
                        else
                        {
                            int value;
                            if (bmTable.TryGetValue(ipString[inputIndex], out value))
                            {
                                inputIndex = startIndex + value;
                            }
                            else
                            {
                                inputIndex = startIndex + pLength;
                            }
                            isMatch = false;
                        }
                    }

                    if(isMatch) // pattern found!!
                    {
                        int value;
                        if (pList.TryGetValue(pString, out value))
                        {
                            pList[pString] = value + 1;
                        }
                        else
                        {
                            pList.Add(pString, 2);
                        }

                        inputIndex = startIndex + 1;
                        
                    }

                }
                else
                {
                    int value;
                    if (bmTable.TryGetValue(ipString[inputIndex], out value))
                    {
                        inputIndex = startIndex + value;
                    }
                    else
                    {
                        inputIndex = startIndex + pLength;
                    }
                }

                patternIndex = pLength - 1;
                isMatch = true;
                startIndex = inputIndex;
            }

        }

        /* 
        * Name: 
        *      FindPattern_UsingBinaryTree
        * Definition: 
        *      This function iterates the input string and uses the Binary Tree Search Algorithm
        *      to find the count of a pattern string. 
        * Input Parameters:
        *      1) inputStr: this is the input string to look for the pattern.
        *      2) pLength: this is the length of the pattern for conducting the search in the input string.
        * Output Paramters:      
        *      1) patternList: this contains the list of patterns found in the input string along with their count, 
        *         in a (key,value) pair.
        * Return Type:
        *      Void: No return type since the 'patternList' is a reference-type object.
        */
        static void FindPattern_UsingBinaryTree(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);

                for (int i = 0; i <= inputStr.Length - pLength; i++)
                {
                    string searchString = inputStr.Substring(i, pLength); // this is the pattern the needs to be searched in the input string                               

                    if (BinaryTreeSearch(searchString))
                    {
                        int value;
                        if (patternList.TryGetValue(searchString, out value)) // check if the pattern has NOT already been found before
                        {
                            patternList[searchString] = value + 1;
                        }
                        else
                        {
                            patternList.Add(searchString, 2);
                        }
                    }
                }
            }

            catch (Exception)
            {
                throw;
            }
        }

        /* 
        * Name: 
        *      BinaryTreeSearch
        * Definition: 
        *      This function searches for a pattern string using the Binary Tree creation/searching approach
        *      and returns true or false. If the pattern is found, it returns true else it adds the pattern to 
        *      the existing binary tree at an appropriate position.
        * Input Parameters:
        *      1) patternStr: this is pattern string to look for in the Binary Tree.
        *      2) pLength: this is the length of the pattern for conducting the search in the input string.
        * Return Type:
        *      Bool: true if the pattern is found in the string, false otherwise.
        */
        public static bool BinaryTreeSearch(string patternStr)
        {
            bool stringFound = false;
            bool nodeCreated = false;

            if (RootNode != null)
            {
                BinaryTreeNode nextNode = RootNode;

                while (!stringFound && !nodeCreated && nextNode != null)
                {
                    int comparisonResult = string.Compare(patternStr, nextNode.pData);
                    if(comparisonResult == 0)
                    {
                        stringFound = true;
                        break;
                    }
                    else
                    {                        
                        if (comparisonResult > 0) 
                        { 
                            if(nextNode.right_node == null)
                            {
                                BinaryTreeNode newNode = new BinaryTreeNode(patternStr);
                                nextNode.right_node = newNode;
                                nodeCreated = true;
                            }

                            nextNode = nextNode.right_node;
                        }
                        else
                        {
                            if (nextNode.left_node == null)
                            {
                                BinaryTreeNode newNode = new BinaryTreeNode(patternStr);
                                nextNode.left_node = newNode;
                                nodeCreated = true;
                            }

                            nextNode = nextNode.left_node;
                        }
                    }
                }
            }
            else
            {
                RootNode = new BinaryTreeNode(patternStr);               
            }

            return stringFound;
        }

        /* 
        * Name: 
        *      CleanUpBinaryTree
        * Definition: 
        *      This recursive function deletes all the nodes associated with the Binary Tree, except the root node.
        * Input Parameters:
        *      1) node: this is node object from where the cleanup begins (usually the root of the tree).
        * Return Type:
        *      Void: nodes are set to null during the recursive function calls.
        */
        public static void CleanUpBinaryTree(BinaryTreeNode startNode)
        {
            if (startNode.left_node == null & startNode.right_node == null)
            {
                return;
            }
            else
            {
                if(startNode.left_node != null)
                {
                    CleanUpBinaryTree(startNode.left_node);
                    startNode.left_node = null;
                    
                }

                if (startNode.right_node != null)
                {
                    CleanUpBinaryTree(startNode.right_node);
                    startNode.right_node = null;
                }
            }            
        }

        //'Node' class for Approach #5: Binary Tree Search
        public class BinaryTreeNode
        {
            public BinaryTreeNode left_node;
            public BinaryTreeNode right_node;
            public string pData;

            public BinaryTreeNode()
            {
                left_node = null;
                right_node = null;
                pData = string.Empty;
            }

            public BinaryTreeNode(string data)
            {
                left_node = null;
                right_node = null;
                pData = data;
            }
        }

        //Root of the Binary Tree Search
        public static BinaryTreeNode RootNode { get; set; }

        /* 
        * Name: 
        *      DisplayResult
        * Definition: 
        *      This function is used to display the results of various approaches to the problem.
        * Input Parameters:
        *      1) message: to display the approach details to the console.
        *      2) result: the output list in the dictionary format (key-value pair) that contains the pattern name and their respective count
        * Return Type:
        *      Void: output is directly printed to the console.
        */
        static void DisplayResult(string message, Dictionary<string, int> result)
        {
            Console.WriteLine("\n\n\t*********************************************\n\t{0} \n", message);
            if (result.Count == 0)
            {
                Console.WriteLine("\tNo matching patterns found.");
            }
            else
            {
                Console.WriteLine("\tNumber of patterns found = " + result.Count + "\n");
                Console.WriteLine("\t\tPattern String \t\t| \tCount");
                Console.WriteLine("\t____________________________________________________\n");
                
                foreach (KeyValuePair<string, int> patternEntry in result)
                {
                    Console.WriteLine("\t\t\t\"" + patternEntry.Key + "\"\t  \t\t\t  " + patternEntry.Value);
                }
            }
        }

        public static void Main(string[] args)
        {            
            string inputString, patternLengthStr, errorMsg = string.Empty;
            Dictionary<string, int> patternMatchResult = new Dictionary<string, int>();
           
            Console.WriteLine("\n\t Welcome to Pattern Matching/Repeat Approach \n");
            Console.WriteLine("\t Assumptions: ");
            Console.WriteLine("\t\t 1) Pattern matching is case-sensitive.");
            Console.WriteLine("\t\t 2) Input string does not have any trailing or leading white spaces.");
            Console.WriteLine("\t\t 3) Empty white space in a string between 2 words is considered a valid character. \n");
            Console.Write("\t Enter Input String: ");
            inputString = Console.ReadLine().Trim();
            Console.Write("\t Enter Pattern Length: ");
            patternLengthStr = Console.ReadLine().Trim();
                
            // Test Case
            //inputString = "zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=";
            //patternLengthStr = "3";   
                     
            try
            {
                if (!ValidateInputParameters(inputString, patternLengthStr, ref errorMsg)) // validate input before proceeding with the pattern match.
                {
                    Console.WriteLine("\n\t{0}", errorMsg); // Validation failed
                    return;
                }

                //Approach #1: Brute Force -- START

                FindPattern_BruteForce(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 1 - Brute Force:", patternMatchResult);

                //Approach #1: Brute Force -- END

                //Approach #2: Using Recursion -- START

                patternMatchResult.Clear();
                FindPattern_UsingRecursion(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 2 - Using Recursion:", patternMatchResult);

                //Approach #2: Using Recursion -- END

                //Approach #3: Using Regex -- START

                patternMatchResult.Clear();
                FindPattern_UsingRegex(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 3 - Using Regex:", patternMatchResult);

                //Approach #3: Using Regex -- END

                //Approach #4: Using Bayer-Moore Algorithm -- START

                patternMatchResult.Clear();
                FindPattern_UsingBayerMooreAlgo(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 4 - Using Bayer-Moore Algorithm:", patternMatchResult);

                //Approach #4: Using Bayer-Moore Algorithm-- END           

                //Approach #5: Using Binary Tree -- START

                patternMatchResult.Clear();
                FindPattern_UsingBinaryTree(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 5 - Using Binary Tree:", patternMatchResult);

                //Approach #5: Using Binary Tree -- END     

                Console.WriteLine("\n\n\t-----------------------------End of Program-----------------------------");
            }
            catch (Exception ex)
            {
                Console.WriteLine("Application Exception: {0} \n StackTrace: {1}", ex.Message, ex.StackTrace);
            }
            finally
            {
                if (RootNode != null)
                {
                    CleanUpBinaryTree(RootNode);
                    RootNode = null;
                }
            }                    
        }
    }
}

​x
 
using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
​
namespace FrozenMountain
{
    public class Program
    {
        /* 
         * Name: 
         *      ValidateInputParameters
         * Definition: 
         *      This function validates the input parameters - input string and pattern length.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.    
         * Output Parameters:      
         *      1) errMsg: validation error, if any.
         * Return Type:
         *      bool: True/False is returned along with the validation error message.
         */
        static bool ValidateInputParameters(string inputStr, string pattern, ref string errMsg)
        {
            int pLength;
            if (inputStr == null || inputStr.Length < 2)
            {
                errMsg = " Error: Invalid Input Parameters. The input string is empty or invalid.";
                return false;
            }           
​
            if (pattern == null || !(int.TryParse(pattern, out pLength))) {
                errMsg = " Error: Invalid Input Parameters. The pattern length is empty or invalid.";
                return false;
            }
​
            if (pLength < 1)
            {
                errMsg = " Error: Invalid Input Parameters. The pattern length has to be atleast 1.";
                return false;
            }
​
            if (inputStr.Length <= pLength)
            {
                errMsg = " Error: Invalid Input Parameters. The length of the pattern should be less than the length of the input string.";
                return false;
            }
​
            errMsg = string.Empty;
            return true;
        }
​
        /* 
         * Name: 
         *      FindPattern_BruteForce
         * Definition: 
         *      This function uses the brute force method of finding the pattern string
         *      by simply using nested 'for' loops to find the pattern. Once the pattern is found, 
         *      the pattern is added to a Dictionary Object called as 'result' or 
         *      its count is incremented by one if it already exists in the dictionary object due to the previous find.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.         
         * Output Parameters:      
         *      1) patternList: this contains the list of patterns found in the input string along with their count, 
         *         in a (key,value) pair.
         * Return Type:
         *      Void: No return type since the 'patternList' is a reference-type object.
         */
        static void FindPattern_BruteForce(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);
​
                string searchString; // this is the pattern the needs to be searched in the input string
                string patternString; // this is the pattern to compare for equality
​
                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    searchString = inputStr.Substring(i, pLength);
​
                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        int patternCount = 1;
                        for (int j = i + 1; j <= (inputStr.Length - pLength); j++)
                        {
                            patternString = inputStr.Substring(j, pLength);
                            if (searchString == patternString)
                            {
                                patternCount++;
                            }
                        }
​
                        if (patternCount > 1)
                        {
                            patternList.Add(searchString, patternCount); // its a new pattern
                        }
                    }
                }
            }
​
            catch (Exception)
            {
                throw;
            }
        }
   
        /* 
         * Name: 
         *      FindPattern_UsingRecursion
         * Definition: 
         *      This function iterates the input string and  calls a recursive function to 
         *      find the count of a pattern string. Once the pattern is found, the pattern 
         *      and its count is added to the 'patternList' as a (Key, Value) pair.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.
         * Output Parameters:      
         *      1) patternList: this contains the list of patterns found in the input string along with their count, 
         *         in a (key,value) pair.
         * Return Type:
         *      Void: No return type since the 'patternList' is a reference-type object.
         */
        static void FindPattern_UsingRecursion(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);
​
                string searchString; // this is the pattern the needs to be searched in the input string
​
                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    searchString = inputStr.Substring(i, pLength);
​
                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        int patternCount = 1;
                        GetPatternCount(inputStr.Substring(i + 1), searchString, ref patternCount);
                        if (patternCount > 1)
                        {
                            patternList.Add(searchString, patternCount); // its a new pattern
                        }
                    }
                }
            }
            catch (Exception)
            {
                throw;
            }
        }
​
        /* 
        * Name: 
        *      GetPatternCount
        * Definition: 
        *      This function calculates the number of times a pattern occures in an input string recursively. 
        * Input Parameters:
        *      1) inputStr: this is the input string to look for the pattern.
        *      2) patternStr: this is the pattern string.
        * Output Parameters:      
        *      1) patternCount: number of times the pattern string occurs in the input.
        * Return Type:
        *      Void: No return type since the 'patternCount' argument is passed by reference.
        */
        static void GetPatternCount(string inputStr, string patternStr, ref int patternCount)
        {
            if (inputStr == patternStr)
            {
                patternCount++;
                return;
            }
            else
            {
                if (inputStr.IndexOf(patternStr) != -1)
                {
                    patternCount++;
                    GetPatternCount(inputStr.Substring(inputStr.IndexOf(patternStr) + 1), patternStr, ref patternCount);
                }
                else
                {
                    return;
                }
            }
        }
​
        /* 
         * Name: 
         *      FindPattern_UsingRegex
         * Definition: 
         *      This function iterates the input string and  uses the 'Regex' C# class to 
         *      find the count of a pattern string. Once the pattern is found, the pattern 
         *      and its count is added to the 'patternList' as a (Key, Value) pair. 
         *      Since the pattern string can contain special/meta-characters of a regular expression,
         *      Regex.Escape() function is used to treat them as literals.
         * Input Parameters:
         *      1) inputStr: this is the input string to look for the pattern.
         *      2) pLength: this is the length of the pattern for conducting the search in the input string.
         * Output Paramters:      
         *      1) patternList: this contains the list of patterns found in the input string along with their count, 
         *         in a (key,value) pair.
         * Return Type:
         *      Void: No return type since the 'patternList' is a reference-type object.
         */
        static void FindPattern_UsingRegex(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);
​
                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    string searchString = inputStr.Substring(i, pLength); // this is the pattern the needs to be searched in the input string                
​
                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        string regexExpr = inputStr;
                        var patternMatch = Regex.Match(regexExpr, Regex.Escape(searchString));
                        int patternCount = 0;
​
                        while (patternMatch.Success)
                        {
                            patternCount++;
                            regexExpr = regexExpr.Substring(patternMatch.Index + 1);
                            patternMatch = Regex.Match(regexExpr, Regex.Escape(searchString));
                        }
​
                        if (patternCount > 1)
                        {
                            patternList.Add(searchString, patternCount);
                        }
                    }
                }
            }
​
            catch (Exception)
            {
                throw;
            }
        }
​
        /* 
        * Name: 
        *      FindPattern_UsingBayerMooreAlgo
        * Definition: 
        *      This function iterates the input string and  uses the Bayer-Moore Algorithm 
        *      (with bad match table approach) to find the count of a pattern string. 
        * Input Parameters:
        *      1) inputStr: this is the input string to look for the pattern.
        *      2) pLength: this is the length of the pattern for conducting the search in the input string.
        * Output Paramters:      
        *      1) patternList: this contains the list of patterns found in the input string along with their count, 
        *         in a (key,value) pair.
        * Return Type:
        *      Void: No return type since the 'patternList' is a reference-type object.
        */
        static void FindPattern_UsingBayerMooreAlgo(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);
                int shiftPos;
                Dictionary<char, int> badMatchTable = new Dictionary<char, int>();
​
                for (int i = 0; i < inputStr.Length - pLength; i++)
                {
                    string searchString = inputStr.Substring(i, pLength); // this is the pattern the needs to be searched in the input string                               
                    badMatchTable.Clear();
​
                    if (!patternList.ContainsKey(searchString)) // check if the pattern has NOT already been found before
                    {
                        //creating a bad match table
                        for (int j = 0; j < searchString.Length; j++)
                        {
                            int value;
                            shiftPos = Math.Max(1, (pLength - j - 1));
                            if (badMatchTable.TryGetValue(searchString[j], out value))
                            {
                                badMatchTable[searchString[j]] = shiftPos;
                            }
                            else
                            {
                                badMatchTable.Add(searchString[j], shiftPos);
                            }
                        }
                        BayerMooreSearch(searchString, inputStr.Substring(i + 1), badMatchTable, patternList);
                    }
                }
            }
​
            catch (Exception)
            {
                throw;
            }
        }
​
        /* 
        * Name: 
        *      BayerMooreSearch
        * Definition: 
        *      This function uses the Bayer-Moore Algorithm (with bad match table approach) to find the count of a pattern string. 
        *      Once the pattern is found, the pattern and its count is added to the 'patternList' as a (Key, Value) pair. 
        * Input Parameters:
        *      1) ipString: this is the input string to look for the pattern.
        *      2) pString: this is the pattern string.
        *      3) bmTable: this is the bad-match table list to make the appropriate position shifts during the search.
        * Output Paramters:      
        *      1) pList: this contains the list of patterns found in the input string along with their count, 
        *         in a (key,value) pair.
        * Return Type:
        *      Void: No return type since the 'pList' is a reference-type object.
        */
        static void BayerMooreSearch(string pString, string ipString, IDictionary<char,int> bmTable, IDictionary<string, int> pList)
        {
            int pLength = pString.Length;            
            int patternIndex = pLength - 1;
            int inputIndex = pLength - 1;
            int startIndex = inputIndex;
            bool isMatch = true;
​
            while (inputIndex < ipString.Length)
            {
                if (pString[patternIndex] == ipString[inputIndex])
                {
                    while(patternIndex >= 0 && isMatch)
                    {                        
                        if (pString[patternIndex] == ipString[inputIndex])
                        {
                            patternIndex--;
                            inputIndex--;
                        }
                        else
                        {
                            int value;
                            if (bmTable.TryGetValue(ipString[inputIndex], out value))
                            {
                                inputIndex = startIndex + value;
                            }
                            else
                            {
                                inputIndex = startIndex + pLength;
                            }
                            isMatch = false;
                        }
                    }
​
                    if(isMatch) // pattern found!!
                    {
                        int value;
                        if (pList.TryGetValue(pString, out value))
                        {
                            pList[pString] = value + 1;
                        }
                        else
                        {
                            pList.Add(pString, 2);
                        }
​
                        inputIndex = startIndex + 1;
                        
                    }
​
                }
                else
                {
                    int value;
                    if (bmTable.TryGetValue(ipString[inputIndex], out value))
                    {
                        inputIndex = startIndex + value;
                    }
                    else
                    {
                        inputIndex = startIndex + pLength;
                    }
                }
​
                patternIndex = pLength - 1;
                isMatch = true;
                startIndex = inputIndex;
            }
​
        }
​
        /* 
        * Name: 
        *      FindPattern_UsingBinaryTree
        * Definition: 
        *      This function iterates the input string and uses the Binary Tree Search Algorithm
        *      to find the count of a pattern string. 
        * Input Parameters:
        *      1) inputStr: this is the input string to look for the pattern.
        *      2) pLength: this is the length of the pattern for conducting the search in the input string.
        * Output Paramters:      
        *      1) patternList: this contains the list of patterns found in the input string along with their count, 
        *         in a (key,value) pair.
        * Return Type:
        *      Void: No return type since the 'patternList' is a reference-type object.
        */
        static void FindPattern_UsingBinaryTree(string inputStr, string pattern, Dictionary<string, int> patternList)
        {
            try
            {
                int pLength = Convert.ToInt32(pattern);
​
                for (int i = 0; i <= inputStr.Length - pLength; i++)
                {
                    string searchString = inputStr.Substring(i, pLength); // this is the pattern the needs to be searched in the input string                               
​
                    if (BinaryTreeSearch(searchString))
                    {
                        int value;
                        if (patternList.TryGetValue(searchString, out value)) // check if the pattern has NOT already been found before
                        {
                            patternList[searchString] = value + 1;
                        }
                        else
                        {
                            patternList.Add(searchString, 2);
                        }
                    }
                }
            }
​
            catch (Exception)
            {
                throw;
            }
        }
​
        /* 
        * Name: 
        *      BinaryTreeSearch
        * Definition: 
        *      This function searches for a pattern string using the Binary Tree creation/searching approach
        *      and returns true or false. If the pattern is found, it returns true else it adds the pattern to 
        *      the existing binary tree at an appropriate position.
        * Input Parameters:
        *      1) patternStr: this is pattern string to look for in the Binary Tree.
        *      2) pLength: this is the length of the pattern for conducting the search in the input string.
        * Return Type:
        *      Bool: true if the pattern is found in the string, false otherwise.
        */
        public static bool BinaryTreeSearch(string patternStr)
        {
            bool stringFound = false;
            bool nodeCreated = false;
​
            if (RootNode != null)
            {
                BinaryTreeNode nextNode = RootNode;
​
                while (!stringFound && !nodeCreated && nextNode != null)
                {
                    int comparisonResult = string.Compare(patternStr, nextNode.pData);
                    if(comparisonResult == 0)
                    {
                        stringFound = true;
                        break;
                    }
                    else
                    {                        
                        if (comparisonResult > 0) 
                        { 
                            if(nextNode.right_node == null)
                            {
                                BinaryTreeNode newNode = new BinaryTreeNode(patternStr);
                                nextNode.right_node = newNode;
                                nodeCreated = true;
                            }
​
                            nextNode = nextNode.right_node;
                        }
                        else
                        {
                            if (nextNode.left_node == null)
                            {
                                BinaryTreeNode newNode = new BinaryTreeNode(patternStr);
                                nextNode.left_node = newNode;
                                nodeCreated = true;
                            }
​
                            nextNode = nextNode.left_node;
                        }
                    }
                }
            }
            else
            {
                RootNode = new BinaryTreeNode(patternStr);               
            }
​
            return stringFound;
        }
​
        /* 
        * Name: 
        *      CleanUpBinaryTree
        * Definition: 
        *      This recursive function deletes all the nodes associated with the Binary Tree, except the root node.
        * Input Parameters:
        *      1) node: this is node object from where the cleanup begins (usually the root of the tree).
        * Return Type:
        *      Void: nodes are set to null during the recursive function calls.
        */
        public static void CleanUpBinaryTree(BinaryTreeNode startNode)
        {
            if (startNode.left_node == null & startNode.right_node == null)
            {
                return;
            }
            else
            {
                if(startNode.left_node != null)
                {
                    CleanUpBinaryTree(startNode.left_node);
                    startNode.left_node = null;
                    
                }
​
                if (startNode.right_node != null)
                {
                    CleanUpBinaryTree(startNode.right_node);
                    startNode.right_node = null;
                }
            }            
        }
​
        //'Node' class for Approach #5: Binary Tree Search
        public class BinaryTreeNode
        {
            public BinaryTreeNode left_node;
            public BinaryTreeNode right_node;
            public string pData;
​
            public BinaryTreeNode()
            {
                left_node = null;
                right_node = null;
                pData = string.Empty;
            }
​
            public BinaryTreeNode(string data)
            {
                left_node = null;
                right_node = null;
                pData = data;
            }
        }
​
        //Root of the Binary Tree Search
        public static BinaryTreeNode RootNode { get; set; }
​
        /* 
        * Name: 
        *      DisplayResult
        * Definition: 
        *      This function is used to display the results of various approaches to the problem.
        * Input Parameters:
        *      1) message: to display the approach details to the console.
        *      2) result: the output list in the dictionary format (key-value pair) that contains the pattern name and their respective count
        * Return Type:
        *      Void: output is directly printed to the console.
        */
        static void DisplayResult(string message, Dictionary<string, int> result)
        {
            Console.WriteLine("\n\n\t*********************************************\n\t{0} \n", message);
            if (result.Count == 0)
            {
                Console.WriteLine("\tNo matching patterns found.");
            }
            else
            {
                Console.WriteLine("\tNumber of patterns found = " + result.Count + "\n");
                Console.WriteLine("\t\tPattern String \t\t| \tCount");
                Console.WriteLine("\t____________________________________________________\n");
                
                foreach (KeyValuePair<string, int> patternEntry in result)
                {
                    Console.WriteLine("\t\t\t\"" + patternEntry.Key + "\"\t  \t\t\t  " + patternEntry.Value);
                }
            }
        }
​
        public static void Main(string[] args)
        {            
            string inputString, patternLengthStr, errorMsg = string.Empty;
            Dictionary<string, int> patternMatchResult = new Dictionary<string, int>();
           
            Console.WriteLine("\n\t Welcome to Pattern Matching/Repeat Approach \n");
            Console.WriteLine("\t Assumptions: ");
            Console.WriteLine("\t\t 1) Pattern matching is case-sensitive.");
            Console.WriteLine("\t\t 2) Input string does not have any trailing or leading white spaces.");
            Console.WriteLine("\t\t 3) Empty white space in a string between 2 words is considered a valid character. \n");
            Console.Write("\t Enter Input String: ");
            inputString = Console.ReadLine().Trim();
            Console.Write("\t Enter Pattern Length: ");
            patternLengthStr = Console.ReadLine().Trim();
                
            // Test Case
            //inputString = "zf3kabxcde224lkzf3mabxc51+crsdtzf3nab=";
            //patternLengthStr = "3";   
                     
            try
            {
                if (!ValidateInputParameters(inputString, patternLengthStr, ref errorMsg)) // validate input before proceeding with the pattern match.
                {
                    Console.WriteLine("\n\t{0}", errorMsg); // Validation failed
                    return;
                }
​
                //Approach #1: Brute Force -- START
​
                FindPattern_BruteForce(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 1 - Brute Force:", patternMatchResult);
​
                //Approach #1: Brute Force -- END
​
                //Approach #2: Using Recursion -- START
​
                patternMatchResult.Clear();
                FindPattern_UsingRecursion(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 2 - Using Recursion:", patternMatchResult);
​
                //Approach #2: Using Recursion -- END
​
                //Approach #3: Using Regex -- START
​
                patternMatchResult.Clear();
                FindPattern_UsingRegex(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 3 - Using Regex:", patternMatchResult);
​
                //Approach #3: Using Regex -- END
​
                //Approach #4: Using Bayer-Moore Algorithm -- START
​
                patternMatchResult.Clear();
                FindPattern_UsingBayerMooreAlgo(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 4 - Using Bayer-Moore Algorithm:", patternMatchResult);
​
                //Approach #4: Using Bayer-Moore Algorithm-- END           
​
                //Approach #5: Using Binary Tree -- START
​
                patternMatchResult.Clear();
                FindPattern_UsingBinaryTree(inputString, patternLengthStr, patternMatchResult);
                DisplayResult("Output from Approach 5 - Using Binary Tree:", patternMatchResult);
​
                //Approach #5: Using Binary Tree -- END     
​
                Console.WriteLine("\n\n\t-----------------------------End of Program-----------------------------");
            }
            catch (Exception ex)
            {
                Console.WriteLine("Application Exception: {0} \n StackTrace: {1}", ex.Message, ex.StackTrace);
            }
            finally
            {
                if (RootNode != null)
                {
                    CleanUpBinaryTree(RootNode);
                    RootNode = null;
                }
            }                    
        }
    }
}
​

View IL Code