G. Moore Machine

ProblemG_Eng.pdf

문제에서 주어진 식을 그래프 DAG(Directed Acyclic Graph)로 잘 만들어주면, 비교적 쉽게 풀리는 문제다.

한 마디로, 이 문제를 노가다성 문제라고 생각한다.

DAG를 구성하는 방법은 구체적으로 설명하지 않겠다. 까다로울 수 있지만 특별한 알고리즘이 필요한 것도 아니고 사람마다 저마다의 방법이 있을 것이라 생각하기 때문이다.

필자는 A(B|CD(E|_)G)E 가 입력으로 들어오면 아래와 같이 그래프를 구성했다.

그래프를 구성 한 뒤에는 DP(Dynamic Programming)을 통해 해결하면 된다.

그래프를 구성하는 노드의 개수를 $N$이라 하고, 입력으로 주어지는 두 번째 문자열의 길이를 $L$이라 하자.

우선 그래프에서 위상정렬를 통해 각 노드의 순서를 구한 뒤 그 순서대로 처리한다.

다이나믹 배열의 정의는 아래와 같다.

D[i][j] = 노드 i에서 주어진 문자열 j번째 문자까지 만들 수 있다. 없다.

점화식은 따로 설명하지 않겠다.

위 정의로는 언더바(_) 가 없을 때 두 문자열이 매치가 되는지 $O(NL)$ 시간 안에 판별 할 수 있다.

언더바에 대한 처리도 까다롭지 않다.

D[i][j] = _ or alphabet or ! 중 가능한 최고 우선순위

라고 정의를 해보자.

우선 순위는 _ 가 가장 앞서며 alphabet이 다음이고 !가 마지막이다.

이때 D[N][L] 을 출력해주기만 하면 된다.

G.cpp