[18806] 와일드 카드

부제: Wildcard string matching with Fast Fourier Transform

문제 분석

 우선 지문을 읽어봅시다. 길이 25만의 알파벳 소문자 + '$?$' + '$*$'로 구성된 문자열이 두 개 들어옵니다. 문제에서 제시한 조작으로 두 문자열이 '같도록' 하면 됩니다.

 문제에서 제시한 조작(연산)은 세 가지로, 문자 삽입, 문자 삭제, 문자 치환입니다. 그런데 사실 연산이 셋이나 있을 필요가 없습니다. 그 이유는 문자 '$*$'의 성질 때문인데, 이 녀석은 모든 문자이면서 모든 문자열로 취급될 수 있기 때문에 '치환'과 '삽입'의 역할을 대체할 수 있고, 길이가 0인 문자열로 취급될 수도 있기 때문에 '삭제'의 역할을 대체할 수 있습니다. 따라서 가용 연산을 다음과 같이 간단하게, 다시 적어도 됩니다.

• 문자열의 임의의 위치에 있는 문자를 '$*$'로 대체한다.
• 문자열의 임의의 위치에 '$*$'을 추가한다.

 이거면 끝입니다. 증명은 독자에게 맡깁니다

 

 

 $S$와 $T$가 뭐 어떻게 들어오든 문자열 둘을 단 2회의 연산으로 같게 할 수 있습니다.

$S$의 왼쪽과 $T$의 오른쪽에 $*$를 붙입시다($S$의 왼쪽에 $*$를 붙여도 됩니다. 그럼 $T$의 오른쪽에 $*$을 붙입니다). 그러면 $*S, T*$가 되는데, $S$의 왼쪽 $*$를 $T$로 대체하고 $T$의 오른쪽 $*$를 $S$로 대체하면 $TS, TS$가 되어 두 문자열은 같아집니다. 이제 우리가 코딩할 프로그램의 출력은 $0, 1,$ 아니면 $2$뿐이란 사실을 알게 되었습니다. 모든 경우에서 적어도 $2$번만 연산을 하면 두 문자열이 같아진다는데, $3$번 $4$번 $n$번의 경우를 생각할 필요가 있을까요?

 

그런데 생각해 보니 어떤 경우에는 $S$나 $T$의 서로 반대 끝에 $*$가 이미 붙은 입력이 들어올 수 있습니다. 그런 경우엔 모두 추가로 건드릴 필요 없이 답이 $0$입니다.

 $S$와 $T$의 맨 오른쪽, 왼쪽 문자만 적어 보면 이런 꼴들입니다 (저렇게 $2\times 2$ 행렬로 계속 적겠습니다).

$\begin{pmatrix}S_l & S_r \\\ T_l & T_r\end{pmatrix} = \begin{pmatrix}* & ? \\\ ? & *\end{pmatrix}$ $\begin{pmatrix}? & * \\\ * & ?\end{pmatrix}$ $\begin{pmatrix}* & * \\\ ? & *\end{pmatrix}$ $\begin{pmatrix}* & ? \\\ * & *\end{pmatrix}$ $\begin{pmatrix}* & * \\\ * & ?\end{pmatrix}$ $\begin{pmatrix}? & * \\\ * & *\end{pmatrix}$ $\begin{pmatrix}* & * \\\ * & *\end{pmatrix}$

 

어차피 왼쪽 오른쪽 끝 문자 두개씩 해서 4개만 갖고 경우 나누기 시작한 거, 나머지 경우도 다 따져봅시다. 위에서 적지 않은 경우는 다음과 같습니다.

• 0개: $\begin{pmatrix}? & ? \\\ ? & ?\end{pmatrix}$
• 1개: $\begin{pmatrix}* & ? \\\ ? & ?\end{pmatrix}$ $\begin{pmatrix}? & * \\\ ? & ?\end{pmatrix}$ $\begin{pmatrix}? & ? \\\ * & ?\end{pmatrix}$ $\begin{pmatrix}? & ? \\\ ? & *\end{pmatrix}$
• 2개(가로): $\begin{pmatrix}* & * \\\ ? & ?\end{pmatrix}$ $\begin{pmatrix}? & ? \\\ * & *\end{pmatrix}$
• 2개(세로): $\begin{pmatrix}* & ? \\\ * & ?\end{pmatrix}$ $\begin{pmatrix}? & * \\\ ? & *\end{pmatrix}$

 어차피 풀이 해설 비슷하게 적고 있는 글이지만 위 경우에 어떤 값을 내야 하는지 모두 적지는 않겠습니다. 그걸 찾는 것도 또 나름의 재미가 있잖아요. 각 경우에서 '무슨 짓을 해야 둘을 같게 만들까?', 아니면 '무슨 짓을 해도 추가로 문자열을 조작하지 않으면 둘이 같을 수 없는 이유는 무엇일까?' 를 생각하면 좋습니다. 단 이제 중요한 것이 '$*$ 2개(가로)' 부분인데...

 

 $S = *f_0*f_1*...*f_{n-2}*f_{n-1}*$ 의 꼴($f$은 전부 문자열)이라고 합시다. 만약 $T$에 $*$이 한 개 이상 포함되어 있다면 $T$는 다음과 같이 표현할 수 있습니다: $T = T_l*T_r$. 그러면 $T$의 가운데 $*$을 $f_0*f_1*...*f_{n-2}*f_{n-1}$로 변환할 수 있고, $S$의 왼쪽과 오른쪽 $*$을 $T_l, T_r$로 변환할 수 있으므로 둘은 같게 됩니다. 그러니까 이 경우는 제하고 $T$에 $*$이 한 개도 없는 상황을 생각합시다. $S = *f_0*f_1*...*f_{n-2}*f_{n-1}*$ 와 $*$ 와일드카드 없는 $T$, 둘을 어떻게 다루어야 할까요?

 이 경우에서 나올 수 있는 답은 $0$ 혹은 $1$입니다. $T$의 맨 오른쪽에 $*$을 붙여버리면 앞에서 다룬 $\begin{pmatrix}* & * \\\ * & ?\end{pmatrix}$ 꼴이 되므로 바로 해결되고, 이 말은 즉 '$*$ 2개(가로)' 형태는 1회 이하의 조작으로 두 문자열을 같게 할 수 있다는 뜻입니다.

 경우의 수가 두 개 뿐입니다. 만약 두 문자열이 같다면 조작 횟수 0일 테고, 다르면 무조건 1입니다. 그러니까 두 문자열이 같은지 판별만 하면 되는 경우라는 뜻입니다 (이 수많은 경우들 사이에 판별을 하나 딱 끼워넣은 출제자가 존경스러워지는 순간입니다).

 두 문자열을 매칭할 적에는 '*' 와일드카드를 특별히 다룬다거나 할 필요가 없습니다. $S$가 특별히 좋은 꼴을 하고 있기 때문인데 ($*f_0*f_1*...*f_{n-2}*f_{n-1}*$), 와일드카드 사이에 끼어있는 $f_n$들을 $T$에 그냥 뜨문뜨문 매칭해버리고 $f_n$이 매칭되지 않은 빈 공간은 와일드카드 하나와 딱 매칭시켜버리면 모든 매칭이 끝납니다. 대신 $T$와 $f_n$이 매칭된 인덱스는 $f_n$의 인덱스(아래 첨자) 순서와 딱 맞게 매칭되어야 합니다. 다시 말하자면, $f_n$이 $T$와 매칭된 인덱스를 $m_n$이라고 할 때 $i < j$라면 $m_i < m_j$여야 한다는 뜻입니다.

 

 뭘 해야 하는지는 알았고, 어떻게 해야 하는지 생각할 차례입니다.

문자열 매칭

문자열 매칭을 해야 하는데 문제는 여기 와일드카드가 있습니다. 그냥 문자열 매칭이라고 한다면 해싱이나 KMP를 쓰면 되겠지만 해싱은 우선 와일드카드 문자가 들어간 상황에서 안 되고, KMP는 failure function의 효율성이 와일드카드 때문에 개판이 나서 $O(NM)$ 매칭으로 되돌아갑니다. 그 때 구세주처럼 FFT가 등장합니다. FFT로 문자열 매칭을 어떻게 하냐고요? 아이디어는 다음과 같습니다.

 우선 각 소문자 알파벳 a~z를 서로 다른 자연수에 매칭합니다. 그리고 와일드카드 문자 '$?$'는 0으로 둡니다. 두 문자열 $S, T$에 대해서 두 문자 $S[i]$와 $T[i]$를 비교할 때, $S[i]T[i](S[i]-T[i])^2$가 0이면 서로 같고, 0이 아니면 서로 다르다고 할 수 있을 것입니다. 둘 중 하나만 '$?$' == 0이어도 값은 0이 되고, 둘이 같다면 $S[i]-T[i]$가 0이 될 테니까요. 저걸 모든 문자열에 대해서 수행하고 그 결과를 다 더해서 0이 나오면 전체 문자열은 같다고 할 수 있겠죠 (두 문자열의 차를 제곱한 이유가 여기 있습니다. 제곱을 안 하면 어쩌다 차가 상쇄돼서 문자열이 다른데 0인 경우가 생깁니다).

 그래서 식을 다시 써보면 $\sum S[i]T[i](S[i]-T[i])^2 = \sum S[i]^3T[i] - 2\sum S[i]^2T[i]^2 + \sum S[i]T^3[i]$인데, 수열 $\{a_i\}, \{b_i\}$에 대해서 $\sum a_ib_i$는 FFT로 계산할 수 있죠? 합성곱 꼴에서 한쪽을 반전시키면 되잖아요. ($\sum a_i b_{n-i+1} \to \sum a_i b^{\text{reversed}}_i$). FFT 3번 때리면 매칭된 위치를 구할 수 있겠습니다.

더 효율적인 검색

입력으로 들어오는 두 문자열의 최대 길이는 25만입니다. 만약 $S$가 $(*\ *)$ 꼴이고 $T$에 '$*$' 문자가 하나도 없다면 길이 $|T|$짜리 FFT를 최대 $124999\times 3$번 때려야 합니다. $S = *a*a*a*a*...*a*a*a*$인 경우라면요. 그러니까 위에서 설명한 FFT 검색을 무작정 구현해서 넣었다간 큰일납니다.

 지금의 FFT 검색은 처음부터 끝까지 모든 매칭을 탐색합니다. 문제를 풀기 위해 얻어야 하는 것은 해당 패턴이 존재하는 첫 번째 위치이지 모든 위치가 아니기 때문에, 탐색을 앞에서부터 순차적으로 하다가 딱 매칭이 되면 그 패턴으로 검색을 멈추었으면 좋겠습니다. 탐색 구간을 자르면 이러한 구현이 가능합니다. 문자열 $T$에서 패턴 $p$로 검색을 한다 치면 index $0$부터 $|p|-1$까지, $|p|$부터 $2|p|-1$까지... 이렇게 검색하면 패턴 길이까지 더해서 길이 $2|p| -1$짜리 FFT를 여러 번 시행하는 것으로 계산을 줄일 수 있습니다.

 

그렇게 길고 긴 구현을 하면 AC를 받습니다.

18806번: 와일드 카드