2001 Canadian Computing Competition, Stage 1
Problem S5: Post's Correspondence Problem
Let A and B be two sequences of non-empty strings:
A = (a1, a2, ..., an), B = (b1, b2, ..., bn).
Let m be a positive integer. Does there exist a sequence of integers
i1, i2, ..., ik such that m > k > 0 and ai1ai2...aik = bi1bi2...bik?
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.
The first two lines of input will contain m and n respectively, and m x n ≤ 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.
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
Point Value: 10
Time Limit: 10.00s
Memory Limit: 16M
Added: Sep 30, 2008
- String Manipulation
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3