BOJ 6300 단어 퍼즐

Aho-Corasick 알고리즘을 응용하여 풀 수 있는 문제입니다.

Needle의 집합의 문자열들의 길이의 합이 $N$이고 haystack의 길이가 $M$이며 그 안에 needle의 등장 횟수의 합이 $K$이면, Aho-Corasick 알고리즘은 $\mathcal{O} (N+M+K)$에 모든 needle의 모든 등장 위치를 찾을 수 있습니다. 따라서 주어진 $W$개의 단어들로 아호-코라식 트라이를 만든 다음 격자판의 모든 방향을 따라가면서 검색해보면 모든 단어의 모든 위치를 찾을 수 있지만, 이렇게 구현하면 최악 $1000^3$개의 후보 위치를 처리해야 하게 됩니다.

이를 해결하기 위해, 알고리즘을 수정하여 각 needle 단어의 맨 첫 번째 등장 위치만을 처리하도록 할 수 있습니다. Wikipedia의 설명을 따라하면 haystack에서 각 위치에서 끝나는 모든 단어를 확인하기 위해서는 dict suffix link를 반복해서 따라가야 하는데, 이를 따라가면서 만난 노드들에서 단어의 끝 마커와 dict suffix link를 모두 지워 주면 해당하는 단어들은 더 이상 검색되지 않습니다. 해당 정보는 한 줄의 haystack 검색이 끝나면 다시 원복해 줍니다.

그런데 격자에서 역방향으로 갈 때 똑같이 하게 되면 좌표가 가장 작은 위치가 아닌 가장 큰 위치를 찾아버리게 되므로, 모든 단어를 뒤집은 다음 이 단어들로 아호-코라식 트라이를 한 번 더 만들어서 정방향으로 검색해 줍니다.