Відкрити головне меню

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

Формальне визначанняРедагувати

Нехай   — рядок довжини  .

Будь-який рядок  , в якому  , є підрядком   довжини  .

Якщо  , тоді   називається префіксом   довжини  .

Якщо  , тоді  суфікс   довжини  .

ПрефіксРедагувати

Префіксом рядка   називається рядок  , де  . Власний префікс рядка не дорівнює самому рядку ( )[1]; деякі джерела[2] на додаток до цього накладають обмеження непорожньості ( ). Префікс можна розглядати як особливий випадок підрядка.

ПрикладРедагувати

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

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

Отримання підрядкаРедагувати

Якщо 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 0-13-497777-7. 
  2. Гусфілд, Ден (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. США: Кембридж Юніверсіті Прес. ISBN 0-521-58519-8.