The condition in the Problem Statement would be the same if it included non-simple paths. Below, we also consider non-simple paths.

For a path from vertex \(1\) to vertex \(u\), \(p=(v_1,\ v_2,\ \dots,\ v_k)\ (v_1=1,\ v_k=u)\), let \(f(p)\) denote the largest \(i\) such that \((B_1,\ B_2, \dots,\ B_i)\) is a subsequence of \((A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k})\) (or \(0\) if it does not exist). Additionally, let \(d_u\) be the smallest value of \(f(p)\) for a path \(p\) from vertex \(1\) to vertex \(u\).

One can check the condition in the Problem Statement by seeing if \(d_{N}=K\), so our objective is to find \(d_u\ (1\le u \le N)\).

[1] Observation on \(f(p+(u'))\)

Let \(p\) be a path from vertex \(1\) to vertex \(u\), and \(u'\) be a vertex adjacent to \(u\).

For a path from vertex \(1\) to vertex \(u'\), \(p'=(v_1,\ v_2,\ \dots,\ v_k,\ u')\), let us consider \(f(p')\). From the definition, we have \(f(p')=f(p)+1\) if \(A_{u'}=B_{f(p)+1}\) and \(f(p')=f(p)\) otherwise, since the only difference between \(p\) and \(p'\) is the addition of \(A_{u'}\) (remember the greedy strategy for subsequence testing).

From this, for paths \(p\) and \(q\) from vertex \(1\) to vertex \(u\) such that \(f(p) < f(q)\), we have \(f(p+(u')) \leq f(q+(u'))\). Therefore, to determine \(d_{u'}\), concerning the paths via vertex \(u\), we only have to consider the minimum value of \(f(p)\), that is, \(d_u\), and the following holds:

\( d_{u'} =\min_{u} \begin{cases} d_u+1 & (A_{u'}=B_{d_u+1}) \\ d_u & (A_{u'}\neq B_{d_u+1}) \end{cases}. \)

[2] Use 01-BFS

From the above observation, it can be seen that the following algorithm finds \(d_u\). The correctness can be shown similarly to the proof for Dijkstra’s algorithm.

1. Initialize \(d_u\ (u \neq 1)\) to \(K+1\). For \(d_1\), initialize it to \(1\) if \(A_1=B_1\) and \(0\) otherwise.
2. Initialize the set \(S\), which consists of vertices \(u\) such that \(d_u\) is unconfirmed, to \(S=\{1,\ 2,\ \dots,\ N\}\).
3. Repeat the following as long as \(S\) is not empty.
   • Remove from \(S\) the \(u\) with smallest \(d_u\) among \(u \in S\), since \(d_u\) is now confirmed. Then, for each vertex \(u'\) adjacent to \(u\), let \(d_{u'}\leftarrow \min(d_{u'},\ d_u+1))\) if \(A_{u'}=B_{d_u+1}\), and \(d_{u'}\leftarrow \min(d_{u'},\ d_u))\) otherwise.

This can be implemented similarly to 01-BFS to run in \(O(N+M)\) time.