DSA
KMP
O(n+m) substring search
Source board
This definition comes from the board below. Open it to see the term in context.
Arrays and StringsDSAMore terms from this board
- arraycontiguous same-size slots (O(1) index)
- capacity vs lengthallocated vs used
- dynamic arrayauto-growing array (amortized O(1) append, l.01)
- fixed vs variable windowconstant size vs condition-driven
- Floyd's cycle detectionfast/slow pointers
- immutablecan't edit in place (→ += in a loop is O(n²))
- prefix sumcumulative array for O(1) range queries
- sliding windowa growing/shrinking [L..R] range
- stringarray of characters/code points
- StringBuilder / jointhe O(n) fix
- two-pointertwo indices sweeping (converging or fast/slow) → O(n) instead of nested O(n²)