using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        Console.WriteLine(PermutationString("BACDGABCDAB","ABCD"));

        PermuationString2("BACDGABCDAB","ABCD");

    }

    private static void PermuationString2(string a,string b)

    {

        int[] charP = new int[256];

        int[] charT = new int[256];

        for(int i=0;i<b.Length;i++)

        {

            charP[b[i]]++;

            charT[a[i]]++;

        }

        for(int i=b.Length;i<a.Length;i++)

        {

            if ( CompareArray(charP,charT))

                Console.WriteLine("start Index is " + (i-b.Length).ToString());

            charT[a[i]]++;

            charT[a[i-b.Length]]--;

        }

    }

    private static bool CompareArray(int[] a,int[] b)

    {

        for(int i=0;i<256;i++)

        {

            if ( a[i] != b[i] )

                return false;

        }

        return true;

    }

    private static int PermutationString(string a, string b)

    {

        if ( a.Length < b.Length )

            return 0;

        int aLength = a.Length-1;

        int bLength = b.Length-1;

        Dictionary<char,int> hashB = new Dictionary<char,int>();

        for(int i=0;i<b.Length;i++)

        {

            if ( hashB.ContainsKey(b[i]))

            {

                hashB[b[i]]++;

            }

            else

            {

                hashB.Add(b[i],1);

            }

        }

        int count = 0;

        for(int i =0;i<a.Length-b.Length;i++)

        {

            string s = a.Substring(i,b.Length);

            Dictionary<char,int> hashA = new Dictionary<char,int>();

            bool found = true;

            for(int j=0;j<s.Length;j++)

            {

                //Console.WriteLine(s);

                if (!hashB.ContainsKey(s[j]))

                {

                    found = false;

                    break;

                }

                if ( hashA.ContainsKey(s[j]))

                {

                    hashA[s[j]]++;

                }

                else

                {

                    hashA.Add(s[j],1);

                }

            }

            if ( found == true  )

            {

                Console.WriteLine(s);

                foreach(var item in hashB)

                {

                    int temp = hashA[item.Key];

                    if ( temp != item.Value )

                    {

                        found = false;

                        break;

                    }

                }

            }

            if ( found == true)

            {

                count++;

            }

        }

        return count;

    }

}