MAC0122 Desenvolvimento de Algoritmos
ordem alfabética, mas isso não está correto.) Por exemplo, a seguinte lista de strings está em ordem lexicográfica:
a ab abc abcd abd ac acd ad b bc bcd bd c cd d
Para definir a ordem lexicográfica de maneira precisa, é preciso entender bem a ordem entre os caracters das strings. Vamos nos restringir aos caracteres da tabela ISO-LATIN-1. Cada caracter é representado por um byte e portanto tem um valor entre 0 e 255. Isso torna possível comparar caracteres e dizer se um é menor ou maior que outro. Por exemplo, '5' < 'A', 'A' < 'B', 'a' > 'B', 'z' < 'ã' e 'ç' > 'ã'.
Dizemos que uma string s é lexicograficamente menor que uma string t se o primeiro caracter de s que difere do correspondente caracter de t é menor que o caracter de t. Assim, para decidir se s é lexicograficamente menor que t basta procurar a primeira posição, digamos k, em que as duas strings diferem. Se s[k] < t[k] então s é lexicograficamente menor que t. Se s[k] > t[k] então t é lexicograficamente menor que s. Se k não está definido então s e t são iguais ou uma é prefixo próprio da outra; no segundo caso, a string mais curta é lexicograficamente menor que a mais longa.