New answers tagged

0

I've copied below the wikipedia algorithm for computing the LPS array (which is usually called the failure function because in the main KMP algorithm you refer to this table whenver there's a failed match). They denote $T[]$ where you use $LPS[]$ algorithm kmp_table: input: an array of characters, W (the word to be analyzed) an ...


3

If reusing strings in $A$ is allowed you can solve it with dynamic programming: First, store strings in $A$ in a prefix tree (just a reversed suffix tree link), and recursively detrmine if $S[i:end]$ can be constructed from $A$: Let $\ell$ be the length of the string, and wlog assume $S$ is appended by $\$$ and $A\gets A\cup \{\$\}$. Moroever, let $m[i]\in\{...


Top 50 recent answers are included