WA / Runtime in CHEATCON [solved]

[fyl]

Hello there!

I’m getting WA trying to solve https://www.spoj.com/problems/CHEATCON/

The approach I’m using is this:

1. Make a graph G out of the regex that was given
   1.1. There are only two types of vertices: letters and non-letters
   1.2. The graph has two fixed vertices: one for start of regex, one for end of regex
2. For each query q, consider DFS on slightly altered graph H:
   2.1. For each vertex u of G and index i of q, there’s a vertex (u, i) in H
   2.2. Two vertices (u, i), (v, j) of H are neighbors if uv is an arc of G and
   2.2.1. v is not a letter and j equals i
   2.2.2. v is i-th letter of q and j equals i+1
3. See if vertices (start of regex, 0) and (end of regex, length of q) are connected in H.

I’m already considering that queries can be empty words.
Tried some trivial and non-trivial inputs. Answers seem alright.
Problem statement says that there should be an empty line after each test case, but example output provided doesn’t do that, which is weird.

Anyways, here is the code.

- code removed -

[fyl]

Hi again,
So I prodded this code here and there for a while and ended up using Dijkstra’s shunting-yard algorithm to parse the regex into infix notation, and then using this to make a graph where traversal means accepting the string.

Problem is, now I’m getting runtime error. Why?
From my calculations, allocated space is enough. Besides the two special vertices for start and end of regex, I’m making at most two more vertices for each symbol in the regex. So 400 vertices should be enough, no?
Unless there’s a malformed regex in some input, I can’t see how this would lead the prog into a runtime error. Is it possible that a test case doesn’t conform to the problem statement? Or am I assuming something I shouldn’t about the input cases?

[tjm]

Comparing against real regexp engine with random test cases don’t show any differences.

I would try trimming whitespace characters from input (I think it will give wrong answers for test cases with CR LF line endings for example).

[fyl]

Spot on! (:
The runtime error was caused by an input sanitization issue. Thanks for your answer.

(unfortunately, now I’ve still got a WA in my hands to solve instead ): )

[tjm]

There are regexp patterns longer than 150 characters.

[fyl]

Finally got that elusive AC! (:
Thank ya, bud.

I wonder what did the problem statement mean by “First line of a test case contains a regex (defined before, between 1 and 150).”, though.