The x [i] represents the i-th character of the string x, note that the subscript here starts from 1. Define a function Match [i, j], indicating whether the prefix of the length of the feature string X is a prefix that is the length of the length j in the string. After analysis, the following recursive formula is written: Match [i, j] = match [i-1, j-1], IF x [i] = '?' = Match [i-1, 1..j] Any one is equal to TRUE, IF x [i] = '*' = match [i-1, j-1] and (x [i] = s [j]), IF x [i] is not a wildcard, the border of the recursive formula Condition is Match [0,0] = true, match [i, 0] = match [i-1, 0], IF x [i] = '*' = false, Otherwise
According to the recursive formula and boundary conditions above, it is easy to write a dynamic planning algorithm to determine whether or not the regular expression X matches the string S. The complexity of this algorithm is O (MN), where M, N are the length of X and S, respectively.
