Good day codeforces.
I am currently preparing a problem where a variable must match one of the ten possible values. Once I finished the validator, I noticed that it validates unusually long, about 18 seconds. Meanwhile, my solution only runs in about 2 seconds on my local machine.
After debugging, I found out that the problem is with readToken. I created a simple validator to reproduce the bug:
Validator 1: https://ideone.com/1CZiQW
Validator 2: https://ideone.com/d91Aan
test-case used: https://files.catbox.moe/qb00ce.in (size: 5.2 MB)
What both of them do is read an input file where the first variable (cmd) can be one of ten values (QUERY1 — QUERY10). Their running time differ vastly.
Validator1:
time ./a.out < testcase.in
real 0m16,480s
user 0m16,465s
sys 0m0,009s
Validator2:
time ./a.out < testcase.in
real 0m1,667s
user 0m1,662s
sys 0m0,005s
As we can see, Validator2 is almost ten times faster than validator1. Is there a caveat on readToken() which makes it slow to validate multiple patterns? i tried readToken([A-Z0-9]*) and it gives compatible results to validator2.
Thank you for your time, and have a nice day :)