Find the smallest window in a string containing all characters of another string

#include <stdio.h>

typedef struct {
const char *start, *end;
}Window;


static int isAllPresent(int a[]) {

int i;

for(i = 0; i < 128; ++i)
if(a[i] != 0 && a[i] != -1)
return 0;

return 1;
}

Window minWindow(const char *haystack, const char *needle) {

Window r = {NULL, NULL}, cur;

int count[128], i;

const char *p = needle;

char c;

/*
        find the count of the chars in needle
    */
for(i = 0; i < 128; ++i)
count[i] = -1;

while((c = *p++)) {
i = count[c];
count[c] = ((i == -1) ? 1 : (i + 1));
}


//find the first character of the needle in haystack
while((c = *haystack)){
if(count[c] != -1) break;

haystack++;
}

if(c == '') return r;

cur.start = haystack;

while((c = *haystack) ) {

if(count[c] != -1) { //if it presents

if(count[c] == 0){//this char count is zero, then we have to skip upto the same character in window

p = cur.start;

while(*p != c) { //till the current character not find

if(count[*p] != -1) {
count[*p]++;
}
p++;
}

p++; //move to the next char

while(p < haystack && count[*p] == -1 ) { //find the first character persents in needle
p++;
}
cur.start = p;

} else { //we can accomdate this character
count[c]--;
}

if(count[c] == 0 && isAllPresent(count)) { //if the window has all the chars of needle
cur.end = haystack;

if(r.start == NULL || (r.end - r.start) > (cur.end - cur.start))
{
r = cur;
}
}
}

haystack++;
}

return r;
}


int main() {

Window r = minWindow("this is a test string", "tsist ");

if(r.start) {
while(r.start <= r.end) {
printf("%c", *r.start);

r.start++;
}
printf("\n");
}

return 0;
}
Advertisements

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