# Post Correspondence Problem - algorithm that solves the problem for a word with maximum K length

The question is as follows:

Let's observe the following Post correspondence problem.

Input: Two finite lists of words $A$ and $B$ and a natural number $k$.

Question: Is there any words correspondence with a length of $k$ at the maximum?

Describe an algorithm to solve the problem and analyze its runtime.

I really don't understand how to solve this problem. From my understanding, the Post correspondence problem is undecidable so how come we can describe an algorithm to solve this question?

PCP is undecidable essentially because, if there is a match, it could be arbitrarily long. But, here, the question specifically excludes any string longer than $k$ characters. There are only about $2^{k+1}$ possible strings of length at most $k$ over alphabet $\{a,b\}$. Does that help you find an algorithm?