Subsequências e subvetores

Uma subsequência é o que sobra quando alguns termos de uma sequência são apagados.  Mais precisamente, uma subsequência de uma sequência  (a1, a2, … , an)  é qualquer sequência  (s1, s2, … , sk)  tal que 

s1 = ai1s2 = ai2,  … ,  sk = aik

para alguma sequência  i1 < i2 < … < ik  de índices.   Por exemplo,  (2, 3, 5, 8)  é uma subsequência de  (1, 2, 3, 4, 5, 6, 7, 8).

O conceito de subvetor é essencialmente o mesmo, uma vez que um vetor é essencialmente o mesmo que uma sequência (a diferença é apenas de notação).  Assim, um subvetor de um vetor  a[1 .. n]  é qualquer vetor  s[1 .. k]  tal que 

s[1] = a[i1],  s[2] = a[i2],  … ,  s[k] = a[ik]

para alguma sequência  i1 < i2 < … < ik  de índices.   Se k = 0, o subvetor é vazio.

Segmentos

Um segmento de uma sequência é uma subsequência contígua:  é o que sobra quando alguns dos termos iniciais e alguns dos termos finais da sequência são apagados.  Mais precisamente, uma segmento de uma sequência  (a1, a2, … , an)  é qualquer sequência da forma  (ai, ai+1, … , ak)  com  1 ≤ ikn.   Por exemplo,  (2, 3, 4, 5)  é um segmento de  (1, 2, 3, 4, 5, 6, 7, 8).

Analogamente, um segmento de um vetor  a[1 .. n]  é qualquer vetor da forma  a[i .. k]  com  1 ≤ ikn.   Se i > k, a expressão a[i .. k] representa o segmento vazio.

Prefixo e sufixo

Um prefixo de uma sequência é um segmento que contém o primeiro termo da sequência.  Um sufixo de uma sequência é um segmento que contém o último termo da sequência.