Wildcard('?', '*') 패턴 매칭 알고리즘

# Wildcard('?', '*') 패턴 매칭 알고리즘

Wildcard가 들어간 패턴과 주어진 문자가 해당하는지 확인하는 알고리즘 중

매칭테이블로 이를 구현하는 것에 대해 알아본다.

1. 문제의 정의

- "ABC" == "ABC": 문자열 모두 동일하다면 True

- "ABC" == "A?C": 문자열 중 ?가 있는 한글자만 빼고, 나머지는 동일하다면 True

- "AC" == "A*C", "ABBBC" == "A*C": 문자열 중 *가 있는 부분이 없거나 여러개인 경우, 나머지는 동일하다면 True

2. 매칭테이블

Dynamic Programming 기법으로서 이전의 문자열까지의 비교를 누적하고, 다음문자를 비교할때 이를 참고한다.

Matching Table		0	1	2	3	...	m
			A	?	C	...	*
0		T(0,0)	T(0,1)	T(0,2)	T(0,3)	...	T(0,m)
1	A	T(1,0)	T(1,1)	T(1,2)	T(1,3)	...	T(1,m)
2	B	T(2,0)	T(2,1)	T(2,2)	T(2,3)	...	T(2,m)
3	C	T(3,0)	T(3,1)	T(3,2)	T(3,3)	...	T(3,m)
...	...	...	...	...	...	...	...
n	Z	T(n,0)	T(n,1)	T(n,2)	T(n,3)	...	T(n,m)

T(n, m)가 패턴 매칭의 결과가 된다.

3. 매칭의 조건

- case1: text[0] == pattern[0] 이면, T(0,0) = True 라고 본다.

             공백과 공백의 비교는 True라고 본다.

             하지만, 물론, 공백과 공백이 아닌 문자의 비교는 False이다.

- case2: text[i] == pattern[j]  이면, T(i, j) = T(i-1, j-1) 을 따른다.(대각선 상속)

              자기 위치의 문자와, 이전까지 문자열이 매칭되고 있었는지의 누적결과도 확인하는 것이다.

- case3: pattern[j] == ? 이면, T(i, j) = T(i-1, j-1) 을 따른다.(대각선 상속)

              ?의 패턴은 아무문자나 가능하고 그 개수만 맞으면 되기 때문에 이전까지의 누적결과만 확인하면 된다.

- case4: pattern[j] == * 이면, T(i, j) = T(i, j-1) 혹은 T(i-1, j) 을 따른다.(옆 또는 위 상속)

              T(i, j-1) 는 * 의 자리에 특정문자가 추가될 수 있음을 나타내고, 그 이전까지의 누적결과는 괜찮았는지 확인하는 것이다.

              T(i-1, j) 는 * 가 공백에 매칭되고 있음을 나타내고, 그 이전까지의 누적결과는 괜찮았는지 확인하는 것이다.

- case5: pattern[1] == * 이면, T(0, j) = T(0, j-1) 을 따른다.(옆 상속)

              패턴이 *로 시작하면 다음 pattern[2] 까지 문제없음을 전달하기 위함이다.

4. 다양한 case 확인해보기

---

Reference:

- https://www.geeksforgeeks.org/wildcard-pattern-matching/

- https://www.youtube.com/watch?v=3ZDZ-N0EPV0