Input
Alphabet $A$.
Two tuples $s$ and $t$ of equal length containing strings over $A$.
For bounded problem: $k \in \mathbb{N}$.
Output
Decision version
True or False.
Non-decision version
Indices: $\{0, 1, \ldots, |s| \}$.
Any tuple of indices $(i_0, i_1, \ldots, i_n)$ so that
$ \oplus_{j=0}^n \, s[i_j] = \oplus_{j=0}^n \, t[i_j] $
where $\oplus$ means concatenate and
$s[i_j]$ means the element of $s$ at index $i_j$.
So, $1001 \oplus 00$ is $100100$.
If no such tuple of indices exists, return False.
Algorithm
For the bounded problem.
Exercise
Write a Python function called corresponds.
It should take two lists of the same length containing strings over the same alphabet.
It shouls also take a positive integer k.
It should return any list (of length at most k) of indices of the two lists such that it solves the Post Correspondence Problem.
If there is none, the function should return False.