All-subsequence embedding kernel ($K(x,y)={\sum }_u{\varphi }_u(x){\varphi }_u(y)$)

Here ${\varphi }_u(x)$ counts increasing position embeddings of the word $u$ as a subsequence of $x$. Counting embeddings retains repeated-letter multiplicities. The empty word has one embedding in every string. Prefix dynamic programming computes this positive-semidefinite kernel by $F(i,j)=F(i-1,j)+F(i,j-1)-F(i-1,j-1)+1_{\{x_i=y_j\}}F(i-1,j-1)$ with boundary values one. The time complexity is $O(|x||y|)$ arithmetic operations, and rolling rows require $O(\min (|x|,|y|))$ integer cells. Counting pairs of position subsets bounds output bit length by $O(|x|+|y|)$.