Example: Regular Expression Matching - rFronteddu/general_wiki GitHub Wiki

You are given a pattern consisting of characters and two special characters:

• "*" matches 0 or more occurrence of the character before *
• "." matches a single character

Example: Input X

1	2	3	4	5	6
x	a	a	b	y	c

Pattern P

1	2	3	4	5	6
x	a	*	b	.	c

Solution Table:

---		0	1	2	3	4	5	6
			x	a	*	b	.	c
0		T	F	F	F	F	F	F
1	x	F	T	F	T	F	F	F
2	a	F	F	T	T	F	F	F
3	a	F	F	F	T	F	F	F
4	b	F	F	F	F	T	F	F
5	y	F	F	F	F	F	T	F
6	c	F	F	F	F	F	F	T

• d[0,0] is true because an empty input matches an empty pattern, the rest of the first column and row are false because an empty pattern cannot match a string and vice versa
• if x[i] == p[j] the overall pattern matches if the input and pattern without these two match -> d[i,j] = d[i-1,j-1]
• if p[j] == "*" we have two options
  • 0 occurrences: we have to check if the entry without the * and the character that precedes it match -> if d[i, j-2] == true -> d[i,j] = d[i, j-2]
  • Otherwise, we check if 1 or more occurrences match:
    • x[i] == p[j-1] || p[j-1] == "." ? if yes, we consider the pattern without i -> d[i,j] = d[i-1,j]
• if p[j] == "." we can ignore this and see if the previous pattern string matched d[i,j] = d[i-1,j-1]
• if x[i] != p[j] && p[j] is not "*" or "." d[i,j] = false since the two can't match

// x[1..n]
// p[1..m]
reg(x,p)
    let d[0..n, 0..m] be a table initialized to False
    d[0,0] = True // empty pattern matches empty string
    n = x.len
    m = p.len
    for i = 1 to n
        for j = 1 to m
            if x[i] == p[j]
                d[i,j] = d[i-1,j-1]
            else if x[i] != p[j] && p[j] != "." && p[j] != "*"
                d[i,j] = False
            else if p[j] == "*"
                if d[i,j-2] == True // 0 occurrences 
                    d[i,j] = True
                else if p[j-1] == x[i] || p[j-1] == "."
                    d[i,j] = d[i-1,j]
            else if p[j] == "."
                d[i,j] = d[i-1,j-1]

    return d[n,m]