1001

1009

1011

1012

$d_{i,j,k}$表示与匹配到$s_i$和$p_j$,k = 0,1,2,表示与前一个交换,不交换,与后一个交换

$d_{i,j,0} = d_{i-1,j-1,2} \text{ and } s_i = p_{j-1}$
$d_{i,j,1} = (d_{i-1,j-1,0} \text{ or } d_{i-1,j-1,1}) \text{ and } s_i = p_{j}$
$d_{i,j,2} = (d_{i-1,j-1,0} \text{ or } d_{i-1,j-1,1}) \text{ and } s_i = p_{j+1}$

这个复杂度是$O(nm)$的,由于状态只有0,1,所以可以用bitset优化i或者j,复杂度$O(nm/64)$