Ronzii's Blog

Just your average geek's blog

Finding the Minimum Window in Text which Contains All Elements from Pattern

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;
int findWindowSize(char t[], char p[])
{
    int text_length = strlen(t);
    int pattern_length = strlen(p);
    int pattern_map[256] = {0};
    int text_map[256] = {0};
    // Count occurences in pattern
    for(int i=0; i<pattern_length; i++)
    {
        pattern_map[p[i]]++;
    }
    int count = 0, minLength = INT_MAX, minIndex = 0, maxIndex =0;
    for(int begin=0,end=0; end<text_length; end++)
    {
        // if character is not present in text, then ignore
        if(pattern_map[t[end]]!=0)
        {
            text_map[t[end]]++;
            // Keep a counter on total length of pattern found till now
            if(pattern_map[t[end]]>=text_map[t[end]])
            {
                count++;
            }
        }
        if(count==pattern_length)
        {
            // Check from the left whether any characters can be ignored
            while(text_map[t[begin]] > pattern_map[t[begin]] || text_map[t[begin]]==0)
            {
                if(text_map[t[begin]]> pattern_map[t[begin]])
                {
                    text_map[t[begin]]--;
                }
                begin++;
            }
            // Calculate minimum
            int min = end-begin+1;
            if(minLength>min)
            {
                minLength = min;
                minIndex = begin;
                maxIndex = end;
            }
        }
    }
    return minLength;
}
int main()
{
    char text[] = "bdacabdccdbac";
    char pattern[] = "ccab";
    cout<<findWindowSize(text,pattern);
    return 0;
}

Advertisements

February 29, 2012 - Posted by | C++ |

No comments yet.

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s