I'd like to ask professional opinion on the following problem — Count String from Hackerrank.

I was able to solve it (at least to produce solution, which passes all testcases). But I am not happy with this solution, because there are testcases where it goes exponential and TLEs. Those testcases are not used to judge the problem, but apparently if it was used in Codeforces or Topcoder round it would have been easily hacked.

Short idea of problem (for more detailed description — follow the link):

• you are given simplified regular expression, not longer then 100 characters
• count number of strings with specific length which match that regular expression. Length can go astronomical (10^9 :)

Solution:

• Because of Length going up to 10^9, the first idea I had was to use Matrix Multiplication
• To use matrix multiplication you need to create DFA graph
• It is easy to build NFA graph from regexp. But you can't use NFA graph to count strings because of epsilon-transitions
• It is easy to convert NFA to DFA getting rid of epsilons

Problem done. Almost. Conversion from NFA to DFA in worst case scenario is exponential. Oops.

Question — is there better approach, which can guarantee polynomial run-time?

There is no editorial for this problem on the site. I don't know if it was used in programming contests.