Приставка

В математике и теории формальных языков приставка (по-английски "prefix") слова — это такая его начальная часть, которой можно дополнить сзади некоторым словом, чтобы получить исходное слово. Формально говорят: слово u является приставкой слова v тогда и только тогда, когда существует слово t такое, что $v = w \cdot t$. Частным случаем является собственная приставка — приставка, отличная от самого слова; иногда выделяют пустую приставку (пустое слово).

Понятие приставки широко используется при изучении строковых алгоритмов, структур данных и теории кодирования. Множество всех приставок слова w фиксируют как $\mathrm{Pref}(w)=\{u\mid\exists v:\;w=u\,v\}$, и это множество важно в построении автоматов, префиксных деревьев (tries), в задачах автодополнения и при анализе префиксных кодов (например, код Хаффмана должен быть префиксным, чтобы обеспечить однозначную декодируемость). В алгоритме Кнута–Морриса–Пратта вычисляется префикс-функция, которая для каждой позиции i строки возвращает длину наибольшей собственной приставки, совпадающей с суффиксом, заканчивающимся в i-й позиции; это формально записывают как $\pi[i]=\max\{k<i\mid s_1\ldots s_k=s_{i-k+1}\ldots s_i\}$ и использует информацию о совпадающих приставках и суффиксах для ускорения поиска подстроки.