서픽스 프리

결정적 유한 오토마타(DFA)는 레이블이 붙은 방향 그래프이다. 즉, 간선을 (p, q) 형태의 방향 간선 대신 (p, q, c) 형태의 삼중항으로 주는데, 여기서 p와 q는 그래프의 노드이고 c는 알파벳의 레이블 문자이다. 각 노드에서 각 문자에 대해 나가는 간선은 최대 하나이다. 다시 말해 (p, q1, c), (p, q2, c), (p, q3, c), … 형태의 간선이 2개 이상 모여 있는 부분집합은 존재하지 않는다. 반면 한 노드는 서로 다른 레이블을 가진 여러 개의 나가는 간선을 가질 수 있다. DFA에서는 하나의 노드가 시작 노드 q0로 지정되고, 노드의 부분집합 F가 최종 노드로 지정된다.

DFA는 튜플 (N, K, M, q0, F)로 표현되는데, N은 상태 집합, K는 입력 알파벳, M은 전이 집합, q0는 시작 상태, F는 승인 상태의 집합이다. DFA D와 문자열 w = w1w2 … wn이 주어졌을 때, w를 만들어 내는 간선의 나열 (q0, q1, w1), (q1, q2, w2), … , (qn−1, qn, wn)이 있고 q**n이 F의 최종 노드이면 D가 w를 승인한다고 말한다. 노드와 간선은 여러 번 방문될 수 있다. 이런 의미에서 DFA는 (유한할 수도, 무한할 수도 있는) 문자열 집합, 즉 DFA가 승인하는 모든 문자열의 집합을 나타낼 수 있다. DFA는 여러 실제 응용에서 유용하다. 예를 들어 소프트웨어 검증이나 패턴 매칭에서는 대상 객체를 DFA로 표현하여 효율적으로 처리하는 경우가 많다.

두 문자열 x와 y에 대해, x = u**y (u와 y를 순서대로 이어붙인 것)인 또 다른 문자열 u가 존재하면 y가 x의 서픽스라고 말한다. 예를 들어 문자열 icpc2018에 대해 icpc2018, cpc2018, pc2018, c2018, 2018, 018, 18, 8, λ는 모두 icpc2018의 서픽스이며, 여기서 λ는 빈 문자열을 나타낸다. 문자열 집합이 서픽스 프리라는 것은 그 집합에 속하는 서로 다른 두 문자열 x와 y 중 y가 x의 서픽스인 쌍이 존재하지 않는다는 뜻이다. 예를 들어 {2018, 18, icpc}는 18이 2018의 서픽스이므로 서픽스 프리가 아니다. 마찬가지로 {λ, icpc2018, icpc}도 λ가 icpc2018과 icpc의 서픽스이므로 서픽스 프리가 아니다. 사실 λ는 모든 비어 있지 않은 문자열의 서픽스이므로, λ와 다른 비어 있지 않은 문자열을 함께 포함하는 집합은 서픽스 프리가 아니다. 또한 정의에 따라 공집합은 항상 서픽스 프리이다.

DFA D가 주어졌을 때, D의 언어 L(D)는 D가 승인하는 문자열의 집합이다. 그러면 L(D)에 속하는 서로 다른 두 문자열 x와 y 중 y가 x의 서픽스가 아닌 쌍이 존재하지 않으면 D가 서픽스 프리라고 말한다. 서픽스 프리는 효율적인 패턴 매칭을 비롯한 여러 응용에서 중요한 역할을 한다. D가 승인하는 문자열이 하나도 없으면 L(D)는 공집합이므로 서픽스 프리이다.

여러분의 과제는 주어진 DFA가 서픽스 프리인지 아닌지를 판별하는 것이다. 오른쪽 그림에서 화살표는 M의 레이블이 붙은 간선(전이)에 대응한다. 예를 들어 간선 (q0, q2, a)와 (q3, q3, b)가 있다. DFA의 유일한 최종 노드가 q2라고 하자. 즉 F = {q2}이다. 경로 (q0, q2, a)가 있으므로 문자열 a는 승인된다. 또한 (q0, q1, b), (q1, q3, b), (q3, q3, b), (q3, q2, a)에 의해 bbb**a도 승인된다. a가 bbb**a의 서픽스이므로 이 DFA는 서픽스 프리가 아니다. 이것이 유일한 예는 아니다. 모든 입력에 대해 DFA의 모든 노드는 시작 노드에서 도달 가능하다고 가정할 수 있다.

프로그램은 표준 입력에서 읽는다. 입력의 첫 줄에는 네 정수 n, m, k, f가 주어지며, n (1 ≤ n ≤ 2,000)은 노드의 수, k (1 ≤ k ≤ 26)는 알파벳 문자의 수, m (1 ≤ m ≤ kn)은 간선의 수, f (1 ≤ f ≤ 2,000)는 최종 노드의 수이다. 그래프의 노드는 0부터 n − 1까지 레이블이 붙으며, 0이 시작 노드이다. 알파벳은 처음 k개의 소문자 영어 글자로 이루어진다. 다음 줄에는 최종 노드 레이블에 해당하는 f개의 정수가 공백으로 구분되어 주어진다. 그다음 m개의 줄에는 각 줄마다 두 정수 p, q와 문자 c가 공백으로 구분되어 주어지며, 레이블이 붙은 간선 (p, q, c)에 해당한다.

프로그램은 표준 출력에 쓴다. D가 서픽스 프리이면 1, 아니면 0을 포함하는 한 줄을 정확히 출력한다.