Підрядок

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

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

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

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

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

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

Префікс

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

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

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

Див. також

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