SUBSTRING

Substring is a contiguous sequence of characters within a string. If s is a string of length n, then a substring can be written as s[i..j] for indices i and j with 0 <= i <= j < n, or as s[i:j] in languages that use Python-like slicing. The length of the substring is j - i + 1. The empty string is a substring of every string.

Substring is distinguished from subsequence: a substring must be contiguous, whereas a subsequence may skip characters while preserving order. In formal language theory, a string x is a substring (also called a factor) of w if there exist strings u and v with w = uxv.

Common operations include extracting a substring and testing whether one string contains another as a substring. In programming, built-in functions or operators such as contains or indexOf implement these checks.

Algorithms for locating substrings range from simple brute-force scans with O(nm) time to more efficient methods. Knuth-Morris-Pratt (KMP) and Boyer-Moore provide linear-time or near-linear time in many cases. Rabin-Karp uses hashing to search for a pattern in O(n + m) on average. For multiple patterns, Aho-Corasick builds a finite automaton. In large texts, suffix trees and suffix arrays support fast substring queries and indexing.

Applications include text search, pattern matching, data mining, and DNA sequence analysis. Substrings are also used in diff utilities, data compression, and string algorithms. Related concepts include superstrings (strings that contain a given substring) and subsequences.