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).
String matching algorithm (Preferably KMP)
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.