Подстрока

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

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

Пусть [math]\displaystyle{ L=c_0\dots c_{n-1} }[/math] — строка длины [math]\displaystyle{ n }[/math].

Любая строка [math]\displaystyle{ S=c_i\dots c_j }[/math], где [math]\displaystyle{ 0\le i\le j\le n-1 }[/math], является подстрокой [math]\displaystyle{ L }[/math] длины [math]\displaystyle{ j-i+1 }[/math].

Если [math]\displaystyle{ i=0 }[/math], то [math]\displaystyle{ S }[/math] называется префиксом [math]\displaystyle{ L }[/math] длины [math]\displaystyle{ j+1 }[/math].
Если [math]\displaystyle{ j=n-1 }[/math], то [math]\displaystyle{ S }[/math] — суффикс [math]\displaystyle{ L }[/math] длины [math]\displaystyle{ j-i+1 }[/math].

Пример

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

Руниверсалис
||||||||||||
|универс||||
||||   |||||
Руни   |||||
       салис

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

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

В языке C

char* subline = ( char* )malloc( end - begin + 2 ); memcpy( subline, line + begin, end - begin + 1 ); subline[ end - begin + 1 ] = '\0';

В языке Python

subline = line[begin:end+1]

В языке python подстрока является слайсом (срезом) (англ. slice, array slicing).

В языке Perl

my $subline = substr $line, $begin, $end - $begin + 1;

В языке PHP

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

В языке Pascal

subline := Copy(line, _begin, _end - _begin + 1);

В языке Ruby

subline = line[start..end]

В языке Java

subline = line.substring(begin,end+1)

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

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

См. также