Pattern Matching

Given a pattern and a string input – find if the string follows the same pattern and return 0 or 1.
Examples:
1) Pattern : “abba”, input: “redbluebluered” should return 1.
2) Pattern: “aaaa”, input: “asdasdasdasd” should return 1.
3) Pattern: “aabb”, input: “xyzabcxzyabc” should return 0.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.Diagnostics;
using System.IO;
using System.Text.RegularExpressions;
namespace ConsoleApplication1
{
    class Program
    {
        public static int flag = 1;
        static void Main(string[] args)
        {
            string pattern = "ababb";
            string input = "thequickthequickquick";
            Hashtable ht = CreateHashTable(pattern);
            int[] frequencyList = new int[ht.Count];
            ArrayList fl = new ArrayList(frequencyList);
            Array patternArray = Array.CreateInstance(typeof(char), ht.Count);
            Array counterArray = Array.CreateInstance(typeof(int), ht.Count);
            ht.Keys.CopyTo(patternArray, 0);
            ht.Values.CopyTo(counterArray, 0);
            Console.WriteLine("Pattern = " + pattern);
            Console.WriteLine("Input = " + input);
            Console.WriteLine("Input Length = " + input.Length);
            Console.WriteLine("===========================");
            getCombinations(pattern, input, patternArray, counterArray, fl, input.Length, ht.Count - 1);
            if (flag == 1)
            {
                Console.WriteLine("Pattern Match Not Found");
            }
        }

        public static void getCombinations(string pattern, string input, Array patternArray, Array counterArray, ArrayList fl, int sum, int index)
        {
            for (fl[index] = 1; (int)fl[index] <= sum / (int)counterArray.GetValue(index) && flag != 0; fl[index] = (int)fl[index] + 1)
            {
                if (index != 0)
                {
                    getCombinations(pattern, input, patternArray, counterArray, fl, sum, index - 1);
                }
                else
                {
                    int currSum = 0;
                    for (int i = 0; i < counterArray.Length; i++)
                    {
                        currSum = currSum + ((int)counterArray.GetValue(i) * (int)fl[i]);
                    }
                    if (currSum == sum)
                    {
                        Console.WriteLine("*** Pattern Length Combination ***");
                        for (int i = 0; i < counterArray.Length; i++)
                        {
                            Console.WriteLine(counterArray.GetValue(i) + " X " + patternArray.GetValue(i) + " --> " + fl[i]);
                        }
                        Console.WriteLine("----------------------------------");
                        flag = 0;
                        Hashtable ht = new Hashtable();
                        Console.WriteLine("*** Pattern Split Up ***");
                        for (int i = 0, j = 0; i < pattern.Length; i++)
                        {
                            if (ht.Contains(pattern[i]))
                            {
                                if (input.Substring(j, (int)fl[GetIndex((char)pattern[i], patternArray)]) != ht[pattern[i]].ToString())
                                {
                                    flag = 1;
                                    break;
                                }
                            }
                            else
                            {
                                ht.Add(pattern[i], input.Substring(j, (int)fl[GetIndex((char)pattern[i], patternArray)]));
                            }
                            Console.WriteLine(input.Substring(j, (int)fl[GetIndex((char)pattern[i], patternArray)]));
                            j = j + (int)fl[GetIndex((char)pattern[i], patternArray)];
                        }
                        if (flag == 0)
                        {
                            Console.WriteLine("Pattern Match Found!!!");
                        }
                        Console.WriteLine("==================================");
                    }
                }
            }
        }

        public static Hashtable CreateHashTable(string pattern)
        {
            Hashtable ht = new Hashtable();
            for (int i = 0; i < pattern.Length; i++)
            {
                if(ht.Contains(pattern[i]))
                {
                    ht[pattern[i]] = int.Parse(ht[pattern[i]].ToString()) + 1;
                }
                else
                {
                    ht.Add(pattern[i], 1);
                }
            }
            return ht;
        }

        public static int GetIndex(char ch, Array patternArray)
        {
            int pos = -1;
            for (int i = 0; i < patternArray.GetLength(0); i++)
            {
                if (ch == (char)patternArray.GetValue(i))
                {
                    pos = i;
                    break;
                }
            }
            return pos;
        }
    }
}

Output
=======
Pattern = ababb
Input = thequickthequickquick
Input Length = 21
===========================
*** Pattern Length Combination ***
2 X a --> 9
3 X b --> 1
----------------------------------
*** Pattern Split Up ***
thequickt
h
==================================
*** Pattern Length Combination ***
2 X a --> 6
3 X b --> 3
----------------------------------
*** Pattern Split Up ***
thequi
ckt
==================================
*** Pattern Length Combination ***
2 X a --> 3
3 X b --> 5
----------------------------------
*** Pattern Split Up ***
the
quick
the
quick
quick
Pattern Match Found!!!
==================================
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s