Hide

Problem G
Deterministic Finite Automata - Concatenation

Accepted submissions to this problem will be granted a score of 12
Languages en is

You are given two deterministic finite automata that accept the languages L1 and L2. You should output the concatenation, a deterministic finite automaton that accepts the language L=L1L2.

Input

The input contains the description of two deterministic finite automata that use the same alphabet. Each is described as follows.

The first line contains four positive integers n, c, s, and f, where n is the number of states, c is the size of the alphabet, s is the initial state, and f is the number of final states. The second line consists of a string Σ=Σ1Σ2Σc of c distinct symbols, each of which is a lowercase english character. The third line consists of f distinct positive integers, the set of final states. Then n lines follow, each with c positive integers, describing the symbol table. The j-th integer on the i-th of those lines represents the state transitioned to from state i upon reading Σj.

Each state is an integer between 1 and n. It is guaranteed that 1sn, and 0fn.

Additionally it is guaranteed the total number of states in the input is at most 21.

Output

Output any deterministic finite automaton representing the concatenation of the input automata. Your output is subject to the same format and restrictions as the input, except it may be larger, allowing nc300000.

You may assume that there exists a non-deterministic finite automata accepting L which can be converted to a deterministic finite automata adhering to these limits using the power set construction without any additional reductions.

Sample Input 1 Sample Output 1
2 2 1 1
ab
1
1 2
2 2
3 2 1 1
ab
2
3 2
3 2
3 3
5 2 1 2
ab
3 4
2 3
2 4
5 3
5 4
5 5
Sample Input 2 Sample Output 2
1 4 1 0
acgt

1 1 1 1
1 4 1 1
acgt
1
1 1 1 1
1 4 1 0
acgt

1 1 1 1
Hide

Please log in to submit a solution to this problem

Log in