substrings

In computer science, a substring of a string S is a contiguous sequence of characters within S. If S has length n, there are n(n+1)/2 substrings in total (counting duplicates). Substrings are typically identified by a starting index i and an ending index j with 1 ≤ i ≤ j ≤ n, written as S[i..j] or Substring(S, i, j).

A substring must be contiguous; a subsequence may skip characters. Prefixes and suffixes are special cases of substrings. For example, in the string "abcdef", "abc" and "def" are substrings, but "ad" is not. Substrings are used for pattern matching, string processing, and many algorithms.

Substring search asks whether a pattern P occurs in a text T. Naive search checks each position and runs in O(|T||P|) time. Efficient algorithms include Knuth-Morris-Pratt, Boyer-Moore, and Rabin-Karp, which aim for near-linear time in practice or worst-case efficiency. To count or enumerate distinct substrings, data structures such as suffix trees, suffix arrays, or suffix automata are used. The maximum number of distinct substrings of a string of length n is n(n+1)/2 (achieved when all characters are distinct). Substrings underpin many tasks in text processing, bioinformatics, and data indexing, where rapid matching and enumeration are essential.