You are given a string T which consists of 0’s and 1’s. Now you input two non-empty strings U and V. Then your task is to match the Regular Expression – U*V with the given string T and find the number of total successful matches.

(NOTE – Here “*” denotes the string of characters of 0 or more length).

### Required Knowledge:

String matching algorithm (Preferably KMP)

### Time Complexity:

O(n^{2})

### Solution with Regular Expression:

A sequence of symbols and characters expressing a string or pattern to be searched for within a longer piece of text.

According to the definition of “*” in regular expression, we note that the number of characters between U and V can range from 0 to |T|-(|U|+|V|). Therefore we can find all positions of occurrence of the strings U and V in T then check among the different occurrences which are possible and then count their number.

[Read more…]