Subșir

În informatică , un subșir este o parte conectată nevid a unui șir .

Definiție formală

Fie un șir de lungime . $L=c_{0}\dots c_{{n-1}}$ $n$

Orice șir unde , este un subșir de lungime . $S=c_{i}\dots c_{j}$ $0\leq i\leq j\leq n-1$ $L$ $j-i+1$

Dacă , atunci se numește prefix de lungime . $i=0$ $S$ $L$ $j+1$
Dacă , atunci este sufixul de lungime . $j=n-1$ $S$ $L$ $j-i+1$

Exemplu

Din punct de vedere informatic, șirurile „ kiped ”, „ Wiki ”, „ diya ” sunt subșiruri ale șirului „ Wikipedia ”; în timp ce „ Wiki ” este un prefix, iar „ diya ” este un sufix.

Wikipedia ||||||||| ||kiped|| |||| ||| Wiki ||| diya

Obținerea unui subșir

Dacă linia este șirul sursă, începutul este indexul primului caracter al subșirului și sfârșitul este indexul ultimului caracter al subșirului, atunci sublinia subșirului se calculează după cum urmează:

În C

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

În Python

subline = line[begin:end+1]

În limbajul python , un subșir este o felie (slice) ( în engleză slice, array slicing ).

În Perl

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

În PHP

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

În Pascal

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

În limbajul Ruby

subline = line[start..end]

În limbajul Java

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

Operații cu subșiruri

Pe lângă sarcina simplă de a extrage un subșir dintr-un șir cu doi indici, există o sarcină mai complexă de a găsi indici care indică un anumit subșir dintr-un șir (căutați o apariție a subșirului într-un șir).