Monday, December 3, 2012

MCPC 2012 - Problem A : Pattern matching

May Allah`s peace , mercy and blessing be upon you

P.S: This is not the original text, I rephrased and summarized the original one because I'm lazy and I couldn't type the whole text. if there is an error it's my mistake.

One of your friends spilled coffee on a form, luckily it wasn't totally destroyed. You will tell him what the fields on his form say for him to fill. You are given all the fields in your form as two strings <label>: <info> and the given questions. Each question is a string that was originally a label in the form but got some of its letters covered by coffee.

Input :
N: number of labels.
N lines : <lable>: <info>
M: number of questions.
M lines: <question>
1<=N<=100, 1<=M<=100, M<=N
<label>,<info> : string of lowercase & uppercase English letters
<question> : string formed of lowercase & uppercase English letters and question mark '?'.

Single line for each question in the following format : <original label>: <original info> that contains the first matching label and the info that matches it.

Example :

Name: Amr Samir
Age: 21
University: Cairo Univ.
Smoker: no
Smoker: no
Name: Amr Samir

Contest Analysis :
The problem seems very simple, the first thing that comes to mind is regular expressions. Yes that's the key, we generate a valid regex from each question by replacing '?' with '.', then look for a match between labels. But the real problem is in treating spaces while reading so you should pay attention to the parsing step. I use a string, usually called gc (garbage collector), to contain unneeded characters.

Solution in C++:
#include <iostream>
#include <fstream>
#include <string>
#include <regex>
#include <algorithm>

#define For(i,n) for(int i(0),_n(n);i<_n;++i)

using namespace std;

int main(int argc, char const *argv[]) {
 long long N,M;
 string gc,labels[100],infos[100],questions[100];
 fstream f("");
 f >> N;
 For(i,N) {
  getline(f,gc,' ');
 f >> M;
 For(i,M) {
 For(i,M) {
  For(j,N) {
   replace(questions[i].begin(),questions[i].end(), '?', '.');
   if(regex_match(labels[j],regex(questions[i]))) {
    cout << labels[j] << ": " << infos[j] << endl;
 return 0;

No comments:

Post a Comment

Zoli Issam's blog proudly powered by Blogger | All rights reserved Jaw,B 2010-2013