FrozenBlood's blog

Hardest Problem About String I Have Ever Encountered
By FrozenBlood, 5 years ago, In English

This problem seems like a regular expression problem. If the constraints were small, it could be easily handled with dynamic programming I think. But it seems almost impossible with this kind of constraints. Any idea?

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it can be done with String Automata, similar to Aho-Corasick

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

This is how I solved this problem:

First you need to tokenize the string with some information. Suppose given string is "1*22#55#8#*#9*". So your tokens will be "1", "22", "55", "8", "9". Now you need some additional information for each token, such as minimum number of digits required, even or odd number of digits required, length of this token etc. So for this token "55" — there should be odd number of digits before this, at least one digit required(since it's odd) etc. And for this token "9" — there should be even number of digits before this, should be at least 2 digits.

Now, for each query string, start finding substring which matches with a token with satisfying other conditions. You just pick the first substring which completely matches with a token. Then start finding next token and so on. If you can find all the tokens in a query string, then the answer is "match", otherwise "not".

You do not require any DP for this, just take the first substring that completely matches with a token and move on to the next token.

See my code for further understanding https://pastebin.com/j9eHmQAP

→ Reply