CCC '01 S5 - Post's Correspondence Problem

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2001 Stage 1, Senior #5

Let A and B be two sequences of non-empty strings: A = (a_1,a_2,\dots,a_n), B = (b_1,b_2,\dots,b_n). Let m be a positive integer. Does there exist a sequence of integers i_1,i_2,\dots,i_k such that m > k > 0 and a_{i_1} a_{i_2} \dots a_{i_k} = b_{i_1} b_{i_2} \dots b_{i_k}? For example, if A = (a, abaaa, ab) and B = (aaa, ab, b), then the required sequence of integers is (2, 1, 1, 3) giving abaaaaaab = abaaaaaab.

Input Specification

The first two lines of input will contain m and n respectively, and m \times n \le 40. The next 2n lines contain in order the elements of A followed by the elements of B. Each string is at most 20 characters.

Output Specification

If a solution exists, print k on a line by itself, followed by the integer sequence in order, one element per line. Otherwise, print a single line containing No solution.

Sample Input 1

7
3
a
abaaa
ab
aaa
ab
b

Sample Output 1

4
2
1
1
3

Sample Input 2

10
3
abc
def
ghi
jkl
mno
pqr

Sample Output 2

No solution.

Comments

There are no comments at the moment.