Home > OS >  optimize regex C
optimize regex C

Time:05-17

i write regex ((((11)*1)((00)*0)(1*)((00)*0)((11)*1))|((0*)11(0*))|(0*)) to check strings like "101111000110000101001110" is divisible by 3, but i have to optimize it

UPD: yes, expression is correct, its question on codewars The 3 possible states

Depending on the current state of X, and the digit (either 0 or 1) we are about to append to the binary form of X, we have our nice DFA of the problem

Now let's play: departing from state "0", we want to travel through the DFA and eventually make our way back to state "0", what are the possible routes?

The routes can be classified into the below 2 categories, in which "[some route]" means it can be repeated:

  1. route a. itself
  2. b. → [d. → [f.] → e.] → c.

Now we are ready to "translate" the possible routes (including route repeatability!) into their corresponding regular expressions:

  1. 0
  2. 1(01*0)*1

Which combines into: 0|1(01*0)*1; we also add to the entire pattern because the pattern itself can also be repeated.

  • Related