Подстрока

В информатике подстрока — это непустая часть строки.

Формальное определение

Пусть L=c0…cn−1{displaystyle L=c_{0}dots c_{n-1}} — строка длины n{displaystyle n}.
Любая строка S=ci…cj{displaystyle S=c_{i}dots c_{j}}, где 0≤i≤j≤n−1{displaystyle 0leq ileq jleq n-1}, является подстрокой L{displaystyle L} длины j−i+1{displaystyle j-i+1}.
Если i=0{displaystyle i=0}, то S{displaystyle S} называется префиксом L{displaystyle L} длины j+1{displaystyle j+1}.
Если j=n−1{displaystyle j=n-1}, то S{displaystyle S}суффикс L{displaystyle L} длины j−i+1{displaystyle j-i+1}.

Пример

С точки зрения информатики строки «кипед», «Вики», «дия» являются подстроками строки «Википедия»; при этом «Вики» — префиксом, а «дия» — суффиксом.

Википедия|||||||||||кипед|||||| |||Вики дия

Получение подстроки

Если line — исходная строка, begin — позиция первого символа подстроки, end — позиция последнего символа подстроки, то подстрока subline вычисляется следующим образом:

В языке C

subline=malloc(end-begin+2);
assert(subline);
memcpy(subline,line+begin,end-begin+1);
subline[end-begin+1]=0;

В языке Python

subline=line[begin:end]

В языке python подстроку называют слайс (англ. slice).

В языке Perl

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

Операции с подстрокой

Помимо простой задачи выделения подстроки из строки по двум индексам существует и более сложная задача поиска индексов, указывающих на заданную подстроку в строке (поиск вхождения подстроки в строку).

См. также