# Tag Info

## New answers tagged substrings

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