pattern matching (codejam round 1A) efficient solution not working

  c++, pattern-matching

I am trying previous year’s codejam question of round 1A

link to question

i have submitted this code(start reading from main method, for ease)-

#include <bits/stdc++.h>

using namespace std;

#define range(t) for (int i = 0; i < t; i++)
#define rangeG(i, t) for (i = 0; i < t; i++)
#define printVec(vec)      
    for (auto c : vec)     
    {                      
        cout << c << endl; 
    }

vector<string> separate(string s)
{
    vector<string> result;
    range(s.size())
    {
        if (s[i] == '*')
        {
            string temp = s.substr(0, i + 1);
            if (temp.size() > 1)
            {
                result.push_back(temp);
            }
            s = s.substr(i, s.size());
            i = 0;
        }
        else if (i == (s.size() - 1))
        {
            string temp = s.substr(0, i + 1);
            result.push_back(temp);
            s = s.substr(i, s.size());
        }
    }
    return result;
}

void removeAsterisk(string &s)
{
    s.erase(remove(s.begin(), s.end(), '*'), s.end());
}

bool setStart(string s, string &start)
{
    bool possible = 1;
    removeAsterisk(s);
    range(min(s.size(), start.size()))
    {
        if (s[i] != start[i])
        {
            possible = 0;
        }
    }

    if (possible)
    {
        if (s.size() >= start.size())
        {
            start = s;
        }
    }

    return possible;
}

bool setEnd(string s, string &end)
{
    bool possible = 1;
    removeAsterisk(s);
    range(min(s.size(), end.size()))
    {
        if (s[s.size() - 1 - i] != end[end.size() - 1 - i])
        {
            possible = 0;
        }
    }

    if (possible)
    {
        if (s.size() >= end.size())
        {
            end = s;
        }
    }

    return possible;
}

void solve()
{
    int n;
    cin >> n;

    vector<string> allS;
    bool possible = 1;

    string start = "";
    string end = "";
    string middle = "";
    string result = "";

    while (n--)
    {
        string str;
        cin >> str;
        if (count(str.begin(), str.end(), '*') == 0)
        {
            result = str;
        }
        vector<string> temp = separate(str);
        for (string s : temp)
        {
            if (s[0] != '*')
            {
                possible = setStart(s, start);
            }
            if (s[s.size() - 1] != '*')
            {
                possible = setEnd(s, end);
            }
            if (possible && count(s.begin(), s.end(), '*') == 0)
            {
                result = s;
                break;
            }
            if (s[0] == '*' && s[s.size() - 1] == '*')
            {
                removeAsterisk(s);
                middle += s;
            }
        }
    }

    if (possible)
    {
        if (result.size() == 0)
        {
            result = start + middle + end;
        }
        cout << result << "n";
    }
    else
    {
        cout << "*n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 0;
    cin >> t;
    range(t)
    {
        cout << "Case #" << i + 1 << ": ";
        solve();
    }
    return 0;
}

it seems correct to me and i have tested many times for many examples, but it is losing in test set-1(exactly one * (asterisk) character and and always the first character of string). Can anyone tell what’s wrong?
you can consider code of first ranked here (it has all solutions,check only for "pattern matching" task) for help. I know that the wrong answer is an edge case and if it passes test set 1 then it will pass others.

Source: Windows Questions C++

LEAVE A COMMENT