HDU : Match the string


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

bool correct = true;
int length;
char input [100000 + 10];

void upto_b (vector <char> &k)
{
    int sz = k.size ();

    if ( sz == 0 || sz == length || input [sz + 1] != 'a' ) {
        correct = false; // 'aba'
        return;
    }

    for ( int i = 0; i < sz; i++ ) {
        if ( k [i] != 'a' ) {
            correct = false;
            return;
        }
    }

}

void upto_h (vector <char> &k)
{
    int sz = k.size ();

    if ( sz == 0 )
        return;

    int cnt_b = 0;
    int cnt_d = 0;

    for ( int i = 0; i < sz; i++ ) {
        if ( k [i] == 'b' )
            cnt_b++;
        else if ( k [i] == 'd' )
            cnt_d++;
    }

    if ( cnt_b > 1 ) {
        correct = false;
        return;
    }

    if ( cnt_b == 1 && k [0] != 'b' ) {
        correct = false;
        return;
    }

    if ( cnt_d == 0 ) {
        correct = false;
        return;
    }

    if ( cnt_b == 0 && cnt_d != sz ) {
        correct = false;
        return;
    }

    if ( cnt_b == 1 && cnt_d != sz - 1 ) {
        correct = false;
        return;
    }
}

void upto_last (vector <char> &k)
{
    int sz = k.size ();

    if ( sz == 0 ) {
        correct = false;
        return;
    }

    for ( int i = 0; i < sz; i++ ) {
        if ( k [i] != 'f' && k [i] != 'k' ) {
            correct = false;
            return;
        }
    }
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);
    getchar ();

    while ( testCase-- ) {
        correct = true;
        gets (input);

        length = strlen (input);
        vector <char> v;
        v.clear ();

        if ( strchr (input, 'b') && strchr (input, 'h') ) {
            int pos = 0;
            for ( int i = 0; input [i] != 'b'; i++, pos++ )
                v.push_back (input [i]);
            upto_b (v);

            v.clear ();
            pos += 2;

            for ( int i = pos; i < length && input [i] != 'h'; i++, pos++ )
                v.push_back (input [i]);

            upto_h (v);

            v.clear ();
            pos++;

            for ( int i = pos; i < length; i++ )
                v.push_back (input [i]);

            upto_last (v);
        }
        else
            correct = false;

        if ( correct )
            printf ("YES\n");
        else
            printf ("NO\n");

    }

    return 0;
}

// @END_OF_SOURCE_CODE

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