(Kind of overkill probably.)

Let n be the length of longer sequence and m be the length of shorter sequence.

First thing we do is deleting all characters from longer sequence that don't apper in shorter sequence in O(n + m) time using hashmap. Now, there are only m symbols left in the "effective alphabet". Also this construction allows us to think that alphabet is just [0, m - 1] (this part seems to be unnecessary if alphabet is something like [0, n - 1], but should reduce hidden constant if alphabet is big enough).

One thing we may notice is that iterating over (i, j) in any kind of lexicographical order is unnecessary: we may iterate over them in order of increasing dp[i][j], which will turn out to be more conventient. This way all dp recalculations will still happen in valid order.

To achieve this, we will use n + 1 queues: queue number k will hold all (i, j) such that dp[i][j] = k. Then we can just iterate k from 0 to n - 1, consider all pairs from k-th queue (there are two types of transitions (i, j, k) -> (i + 1, j, k) just adds new pair in current queue for later consideration, and (i, j, k) -> (i + 1, j + 1, nk > k) is interesting, but affects only later queues).

The difference between this and naive update order is that now queries "find first symbol equal to c in longer string from position p inclusive" happen in increasing order of p. Suppose that we have an array of answers for all such queries for position p. Transition to p + 1 is simple, because only for one symbol answer changes — exactly for symbol at p-th position of longer string. And for it, answer changes to next position of this symbol in longer string. Next positions of each symbol can be precalculated in O(n + m), so we can answer this queries in O(1) after some precalculations, because p only increases.

TL;DR: process states in order of increasing values of dp[i][j], this way start of the query segments always move right, which makes recalculating answers in O(1) possible.