Ta tính KMP automaton ~aut~ của xâu ~s~ trước. Sau đó, công thức DP của chúng ta là ~\text{dp}[i][j][length] = dp[i + 1][j][\text{advance}(length, a[i + 1][j])] + dp[i][j + 1][\text{advance}(length, a[i][j + 1])]~. Hàm ~\text{advance}~ được định nghĩa như sau: ~\text{advance}(length, character) = aut[length][character]~ nếu ~length < |s|~, và ~\text{advance}(|s|, character) = |s|~. Kết quả cần tìm là ~\text{dp}[0][0][\text{advance}(0, a[0][0])]~.

Nếu ta loại trường hợp ~|s| \geq n + m~ thì ta có thể cài đặt KMP automaton trong ~O(|s|^2)~ bằng cách brute force. Lí do: khi ~|s| \geq n + m~ thì số đường đi bằng ~0~, ngược lại ta có thể chứng minh ~|s| \leq 1000~.

Việc chứng minh ~|s| \leq 1000~ là một việc yêu cầu trình độ toán cao. Tuy nhiên ta có thể dễ dàng chứng minh ~|s| \leq 1999~. Lời giải: nếu ~|s| \leq 1000~ ta suy ra ngay ~|s| \leq 1999~, ngược lại ta có ~|s| > 1000 \Rightarrow nm \leq 1000~. Từ đây ta có ~n \leq 1000~ và ~m \leq 1000~, suy ra ~|s| \leq n + m - 1 \leq 1000 + 1000 - 1 = 1999~.

Nếu ta không xét hai trường hợp riêng ra, ta vẫn có thể tính KMP automaton trong ~O(|s|)~ bằng thuật toán KMP.

Định nghĩa KMP automaton: với một xâu ~pattern~, ~aut[length][character]~ là độ dài tiền tố lớn nhất của ~pattern~ sao cho tiền tố đó là hậu tố của ~length~ kí tự đầu của ~pattern~ cộng với ~character~. Đọc thêm tại https://cp-algorithms.com/string/prefix-function.html#building-an-automaton-according-to-the-prefix-function.