Суфікс (інформатика)

В інформатиці підрядок — непорожня зв'язна частина рядка.

Формальне визначання

Нехай ${\displaystyle L=c_{0}\dots c_{n-1}}$ — рядок довжини ${\displaystyle n}$.

Будь-який рядок ${\displaystyle S=c_{i}\dots c_{j}}$, в якому ${\displaystyle 0\leq i\leq j\leq n-1}$, є підрядком ${\displaystyle L}$ довжини ${\displaystyle j-i+1}$.

Якщо ${\displaystyle i=0}$, тоді ${\displaystyle S}$ називається префіксом ${\displaystyle L}$ довжини ${\displaystyle j+1}$.

Якщо ${\displaystyle j=n-1}$, тоді ${\displaystyle S}$ — суфікс ${\displaystyle L}$ довжини ${\displaystyle j-i+1}$.

Префікс

Префіксом рядка ${\displaystyle T=t_{1}\dots t_{n}}$ називається рядок ${\displaystyle {\widehat {T}}=t_{1}\dots t_{m}}$, де ${\displaystyle m\leq n}$. Власний префікс рядка не дорівнює самому рядку (${\displaystyle 0\leq m<n}$); деякі джерела на додаток до цього накладають обмеження непорожньості (${\displaystyle 0<m<n}$). Префікс можна розглядати як особливий випадок підрядка.

Приклад

З точки зору інформатики рядки «кіпед», «Вікі», «дія» є підрядками рядка «Вікіпедія»; при цьому «Вікі» — префіксом, а «дія» — суфіксом.

Вікіпедія ||||||||| ||кіпед|| |||| ||| Вікі дія 

Отримання підрядка

Якщо line — початковий рядок, begin — позиція першого символу підрядка, end — позиція останнього символу підрядка, то підрядок subline вираховується наступним чином:

У мові C

char * subline = (char *)malloc(end - begin + 2); if (subline == NULL) {  fprintf(stderr, "ERROR: malloc failed!");  exit(1); } memcpy(subline, line + begin, end - begin + 1); subline[end - begin + 1] = '\0'; 

У мові Python

subline=line[begin:end+1] 

У мові python підрядок є слайсом (зрізом) (англ. slice).

У мові Perl

$subline = substr($line, $begin, $end-$begin); 

У мові Pascal

SubStr := Copy(SourceStr, StartCharIndex, SubStrLength); 

Операції з підрядком

Окрім простої задачі виділення підрядка з рядка за двома індексами існує і складніша задача пошуку індексів, що вказують на заданий підрядок.

Див. також

• (Рядкові алгоритми)

Примітки

1. Келлі, Дін (1995). Automata and Formal Languages: An Introduction. Лондон: Прентіс-Гол Інтернешнл. ISBN .
2. Гусфілд, Ден (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. США: Кембридж Юніверсіті Прес. ISBN .