문제 태그

• 문자열
• 트라이
• 아호 - 코라식

아이디어

1. 1차원 → 2차원 대응
   • 아호-코라식(AC) 자동화기는 본래 1차원 문자열 집합 매칭용 알고리즘이다.
   • 2차원 격자에서도 "선을 따라 읽는 문자열"을 추출하여 AC에 적용하면 동일하게 동작한다.
2. 8 방향 → 4 방향으로 축소
   • (동, 남동, 남, 북동) 네 방향만 스캔하면 충분하다.
     • 서쪽·북서·북·남서 방향의 단어는 각각 역방향으로 읽은 패턴이 위 네 방향에서 자연스럽게 검출된다.
   • 따라서 트라이(AC 트리)에 원본 패턴과 역순 패턴을 모두 삽입한다.
3. 시작점(Exposed Frontier) 설정

• 방향당 시작점 ≤ L + C이며, 각 선(행·열·대각선)은 정확히 한 번만 스캔한다.

1. 아호 코라식 트리 구현 최적화
   • children: 알파벳 대문자용 26칸 고정 리스트로 dict 대신 인덱스 접근.
   • goto + fail 압축
     • 빌드 단계에서 없는 간선을 모두 실패 링크로 미리 채워두면 검색 중 while fail 루프가 불필요해진다.
2. 검색 단계

for (dx, dy) in directions:          # 4개
    for (sx, sy) in frontier(dx,dy): # ≤ L+C
        x, y, node = sx, sy, root
        while board 경계 안:
            node = node.children[board[x][y]]
            for (pid, rev) in node.output:
                len = |pattern|
                if rev == False:  시작 = (x-(len-1)dx, y-(len-1)dy)
                else:             시작 = (x, y)
                방향 = letter_dir[idx + (4 if rev else 0)]
                사전순으로 최소면 갱신
            x += dx; y += dy

• letter_dir = "A B C D E F G H" (A=북, B=북동 …) 규칙에 맞춰 출력용 문자를 결정한다.

1. 사전순 우선 규칙단어별로 (행, 열, 방향) 3-튜플을 저장하고, 새 후보가 이전 값보다 작을 때 덮어쓴다.Python 튜플 비교는 (행, 열, 문자) 순서로 자동 사전순 비교된다.
2. 복잡도
   • 트리 구축 O(패턴 총 길이)
   • 검색 O(4 × L × C)

정답

from collections import deque
import sys

L, C, W = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(L)]
patterns = [sys.stdin.readline().strip() for _ in range(W)]

directions = [(-1, 0), (-1, 1), (0, 1), (1, 1)]
letter_dir = ["A", "B", "C", "D", "E", "F", "G", "H"]
alph = lambda ch: ord(ch) - 65

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.fail = None
        self.output = []

root = Node()

def insert(word, original, rev):
    node = root
    for ch in word:
        i = alph(ch)
        if node.children[i] is None:
            node.children[i] = Node()
        node = node.children[i]
    node.output.append((original, rev))

for p in patterns:
    insert(p, p, False)
    insert(p[::-1], p, True)

def build():
    q = deque()
    root.fail = root
    for i in range(26):
        if root.children[i]:
            root.children[i].fail = root
            q.append(root.children[i])
        else:
            root.children[i] = root
    while q:
        cur = q.popleft()
        for i in range(26):
            nxt = cur.children[i]
            if nxt:
                nxt.fail = cur.fail.children[i]
                nxt.output += nxt.fail.output
                q.append(nxt)
            else:
                cur.children[i] = cur.fail.children[i]

build()

def search_2d():
    res = {}
    N, M = len(board), len(board[0])
    for idx, (dx, dy) in enumerate(directions):
        if dx == 0 and dy == 1:
            starts = [(i, 0) for i in range(N)]
        elif dx == 1 and dy == 0:
            starts = [(0, j) for j in range(M)]
        elif dx == -1 and dy == 0:
            starts = [(N - 1, j) for j in range(M)]
        elif dx == -1 and dy == 1:
            starts = [(N - 1, j) for j in range(M)] + [(i, 0) for i in range(N - 1)]
        else:
            starts = [(0, j) for j in range(M)] + [(i, 0) for i in range(1, N)]
        for x0, y0 in starts:
            x, y, node = x0, y0, root
            while 0 <= x < N and 0 <= y < M:
                node = node.children[alph(board[x][y])]
                for pat, rev in node.output:
                    Lp = len(pat)
                    if not rev:
                        px = x - (Lp - 1) * dx
                        py = y - (Lp - 1) * dy
                        dch = letter_dir[idx]
                    else:
                        px = x
                        py = y
                        dch = letter_dir[idx + 4]
                    if 0 <= px < N and 0 <= py < M:
                        cand = (px, py, dch)
                        if pat not in res or cand < res[pat]:
                            res[pat] = cand
                x += dx
                y += dy
    return res

matches = search_2d()

for p in patterns:
    x, y, d = matches[p]
    print(f"{x} {y} {d}")