We współczesnych językach programowania znaki są podstawowym typem danych. W pamięci komputera znak jest przechowywany w postaci liczby, którą nazywamy kodem znaku (ang. character code). Każdy znak posiada swój własny kod. Aby różne urządzenia systemu komputerowego mogły w ten sam sposób interpretować kody znaków, opracowano kilka standardów kodowania liter. Poniżej przedstawiamy wybrane dwa:

Znaki są zapamiętywane w postaci 8 bitowych kodów (pierwotnie było to 7 bitów, lecz później standard ASCII został poszerzony na 8 bitów, w których znalazły się różne znaki narodowe). Taki sposób reprezentacji znaków jest dzisiaj bardzo wygodny, ponieważ podstawowa komórka pamięci komputera IBM przechowuje właśnie 8 bitów. Dzięki temu znaki dobrze mieszczą się w pamięci.

8-bitowy kod pozwala przedstawić 256 różnych wartości i tylko tyle może być zdefiniowane znaków w kodzie ASCII. Pierwsza połówka zbioru kodów – od 0 do 127 – jest zdefiniowana na stałe i raczej nigdy nie jest modyfikowana. Jest to tzw. podstawowy zestaw znaków ASCII. Druga połówka – od 128 do 255 – zawiera znaki narodowe, które w różny sposób mogą być przydzielane rozszerzonym kodom ASCII. Z tego właśnie powodu powstały różne strony kodowe. Na przykład konsola znakowa stosuje kodowanie LATIN II. Natomiast system Windows stosuje Windows 1250. Niestety, w obu systemach polskie literki posiadają różne kody. Dlatego wyświetlenie przygotowanego w Windows polskiego tekstu w konsoli znakowej powoduje, iż polskie znaki Windows 1250 zostają źle zinterpretowane w konsoli LATIN II. Problem ten nie występuje w systemach linuksowych (oraz w języku Python, który stosuje kodowanie UTF-8).

Przykładowe programy

program prg;

begin
  writeln('ĄąĆćĘꣳŃńÓ󌜏źŻż');
end.

─ä─ů─ć─ç─ś─Ö┼ü┼é┼â┼ä├ô├│┼Ü┼Ť┼╣┼║┼╗┼╝

#include <iostream>

using namespace std;

int main()
{
  cout << "ĄąĆćĘꣳŃńÓ󌜏źŻż\n";
  return 0;
}

ą╣ĂŠ╩ŕú│нˡîťĆč»┐

Print "ĄąĆćĘꣳŃńÓ󌜏źŻż"
End

ą╣ĂŠ╩ŕú│нˡîťĆč»┐

print("ĄąĆćĘꣳŃńÓ󌜏źŻż")

ĄąĆćĘꣳŃńÓ󌜏źŻż

W języku C++ istnieje funkcja, która ustawia w konsoli znakowej ten sam system kodowania znaków używany przez Windows:

setlocale(LC_ALL, "");

Dzięki niej można tworzyć programy komunikujące się z użytkownikiem w języku polskim:

#include <iostream>

using namespace std;

int main()
{
    setlocale (LC_ALL, "");

    cout << "Zażółć żabią jaźń" << endl;
    return 0;
}

Zażółć żabią jaźń

W tym artykule nie będziemy jednak korzystać z tej funkcji, ponieważ brak jej odpowiedników w innych językach programowania. Nie wpłynie to w żaden sposób na przedstawione tu algorytmy tekstowe. Problem lokalizacji nie sprowadza się jedynie do poprawnego wypisywania polskich literek ą, ć, ę… Obejmuje on również sposób zapisu waluty, dat, liczb ułamkowych, sortowania wg polskiego alfabetu, itp. Problemy te rozwiązuje system operacyjny, jednak program użytkownika musi być napisany w określony sposób. Tym się tutaj nie zajmujemy.

Unicode

Znaki są zapamiętywane w postaci kodów 16-bitowych. Dzięki temu rozwiązaniu liczba możliwych do przedstawienia znaków rośnie do 65536. Pierwsze 256 kodów jest zwykle kompatybilne z kodami ASCII. Kody powyżej 256 tworzą banki znaków, w których znajdują się wszystkie znaki narodowe, arabskie, hebrajskie, matematyczne itp.

Poniższa tabelka prezentuje nazwy typów znakowych w wybranych przez nas językach programowania:

char

widechar
wchar

unsigned char

wchar_t

String * 1

Wstring * 1

x = 10
print(x, type(x)) # Liczba całkowita
x = 10.5
print(x, type(x)) # Liczba rzeczywista
x = True
print(x, type(x)) # Wartość logiczna
x = "Liczba 10"
print(x, type(x)) # Łańcuch znakowy
x = ["x = ", 10, 5.1, False] 
print(x, type(x)) # Lista, itd.

10 <class 'int'>
10.5 <class 'float'>
True <class 'bool'>
Liczba 10 <class 'str'>
['x = ', 10, 5.1, False] <class 'list'>

Zmienne znakowe deklarujemy w identyczny sposób jak zmienne innych typów:

…
var
  c  : char;
  wc : wchar;
…

…
char c;
wchar_t wc;
…

…
Dim c  As String * 1
Dim wc As Wstring * 1
…

Tak zadeklarowana zmienna c może przechowywać jeden znak ASCII, a zmienna wc jeden znak Unicode.

a = "A" # odpowiednik zmiennej znakowej
print("Znak '%s' o kodzie %d" % (a, ord(a)))
a = "ś"
print("Znak '%s' o kodzie %d" % (a, ord(a)))

Znak 'A' o kodzie 65
Znak 'ś' o kodzie 347

c = 0
for i in range(32, 128):
    print(chr(i), end="")
    c += 1
    if c == 32:
        c = 0
        print()

 !"#$%&'()*+, -./0123456789:;<=>?
@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_
`abcdefghijklmnopqrstuvwxyz{|}~

Duże litery: A…Z, kody od 65 do 90
Małe litery: a…z, kody od 97 do 122
Cyfry:       0…9, kody od 48 do 57

Zmienne znakowe mogą również być zadeklarowane jako tablice znaków.

…
var
  c  : array [0..99] of char;
  wc : array [0..99] of wchar;
…

…
char     c[100];
wchar_t wc[100];
…

…
Dim  c As String  * 100
Dim wc As Wstring * 100
…

…
c = "x" * 100
…

W przypadku tablicy znakowej mamy dostęp do poszczególnych znaków za pomocą indeksu w klamerkach kwadratowych. Wyjątkiem jest język Basic, gdzie zmienna znakowa jest traktowana jako spójna całość i dostęp do poszczególnych znaków uzyskujemy poprzez polecenie Mid (przy zapisie do zmiennej) oraz funkcję Mid (przy odczycie ze zmiennej). Pierwszy znak posiada zawsze indeks równy 1.

0

1

2

3

4

5

6

7

A

L

I

G

A

T

O

R

-8

-7

-6

-5

-4

-3

-2

-1

a = "ALIGATOR"
print("a : %s" % a)
print("----------")
for i in range(8):
    print(" a[%d] : '%s'" % (i, a[i]))
print("----------")
for i in range(-1, -9, -1):
    print("a[%d] : '%s'" % (i, a[i]))

a : ALIGATOR
----------
 a[0] : 'A'
 a[1] : 'L'
 a[2] : 'I'
 a[3] : 'G'
 a[4] : 'A'
 a[5] : 'T'
 a[6] : 'O'
 a[7] : 'R'
----------
a[-1] : 'R'
a[-2] : 'O'
a[-3] : 'T'
a[-4] : 'A'
a[-5] : 'G'
a[-6] : 'I'
a[-7] : 'L'
a[-8] : 'A'

a[indeks] = "nowy_znak"

s = "LASEK" # niezmienny łańcuch
print(s)
s = s[:1]+"I"+s[2:] # nowy łańcuch
print(s)

LASEK
LISEK

a = a[:x]+"znak"+a[x+1:]

Przykładowe programy

program prg;

var
  s : array [0..2] of char;

begin
  s[0] := 'A';
  s[1] := 'L';
  s[2] := 'O';
  writeln(s[2], s[1], s[0]);
end.

#include <iostream>

using namespace std;

int main()
{
  unsigned char s[3];
 
  s[0] = 'A';
  s[1] = 'L';
  s[2] = 'O';
  cout << s[2] << s[1] << s[0]
       << endl << endl;
  return 0;
}

Dim s As String * 3
Mid(s, 1) = "A"
Mid(s, 2) = "L"
Mid(s, 3) = "O"
Print Mid(s, 3, 1);
Print Mid(s, 2, 1);
Print Mid(s, 1, 1)
End

s = "ALO"
print(s[2], end="")
print(s[1], end="")
print(s[0])
print()

OLA

Oprócz zwykłych tablic znakowych (ang. character tables), języki Pascal, C++, Basic i Python udostępniają tzw. łańcuchy znakowe (ang. character strings). Są to tablice dynamiczne, które mogą przechowywać ciągi znaków o różnych długościach (łańcuchy automatycznie dopasowują się do rozmiaru przechowywanego tekstu – tablice znakowe natomiast nie posiadają takich cech, programista musi o to zadbać sam):

ansistring

widestring

string

wstring

String

Wstring Ptr

Koniec łańcucha znakowego znaczony jest kodem 0. Znak o tym kodzie nie jest wliczany do łańcucha. Również nie powinieneś tego znaku umieszczać wewnątrz łańcucha, gdyż może to spowodować nieprawidłowe działanie wielu funkcji i procedur tekstowych.

W języku Pascal i Basic indeksy znaków w łańcuchu rozpoczynają się od 1, a w języku C++ i Python od 0. W algorytmach tekstowych musimy wziąć na to poprawkę.

W języku Basic łańcuchy Wstring są wskaźnikami do obszaru pamięci przechowującego właściwe znaki. Dlatego do wskaźnika musi być przypisywany adres zarezerwowanego obszaru, w którym będą umieszczane znaki Unicode. Dostęp do danych następuje poprzez operator *, podobnie jak w języku C++.

Liczbę znaków przechowywanych w łańcuchu tekstowym otrzymamy przy pomocy następujących funkcji:

length(s)

s.length()
s.size()

Len(s)

len(s)

Przykładowe programy

program prg;

var
  s : ansistring;
  i : integer;

begin
  s := 'Hello there!!!';
  for i := length(s) downto 1 do
    write(s[i]);
  writeln; writeln;
end.

program prg;

var
  s : widestring;
  i : integer;

begin
  s := 'Hello there!!!';
  for i := length(s) downto 1 do
    write(s[i]);
  writeln; writeln;
end.

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  s = "Hello there!!!";
  for(int i = s.length()-1; i >= 0; i--)
    cout << s[i];
  cout << endl << endl;
  return 0;
}

#include <iostream>
#include <string>

using namespace std;

int main()
{
  wstring s;
  s = L"Hello there!!!";
  for(int i = s.length()-1; i >= 0; i--)
    cout << (char)s[i];
  cout << endl << endl;
  return 0;
}

Dim s As String
Dim i As Integer

s = "Hello there!!!"
For i = Len(s) To 1 Step-1
  Print Mid(s, i, 1);
Next
Print: Print
End

Dim s As Wstring Ptr
Dim i As Integer

s = Allocate (20 * Len(Wstring))
*s = "Hello there!!!"
For i = Len(*s) To 1 Step-1
  Print Mid(*s, i, 1);
Next
Print: Print
End

s = "Hello there!!!"
for i in reversed(range(len(s))):
    print(s[i], end="")
print()
print()

!!!ereht olleH

Przy przetwarzaniu tekstu często musimy odczytywać kody znaków zawartych w zmiennej znakowej lub zamieniać kody na odpowiadające im znaki – na przykład w celu umieszczenia ich w tekście. W każdym z wybranych przez nas języków programowania istnieją odpowiednie do tego zadania narzędzia.

ord(znak)

chr(kod)

(int)znak

(char)kod

Asc(znak)

Chr(kod)

ord(znak)

chr(kod)

Język C++ traktuje znaki jak liczby całkowite (unsigned char – bez znaku, char – ze znakiem). Nie ma zatem zwykle potrzeby dokonywać konwersji znakowych. Wyjątek stanowi przesyłanie znaków do strumieni –  musimy dokonać konwersji kodu znaku na typ char, aby w strumieniu został zapisany znak, a nie jego kod jako liczba całkowita.

Przykładowe programy

program prg;

var
  s : ansistring;
  i : integer;
begin
  readln(s);
  writeln;
  for i := 1 to length(s) do
    writeln(s[i], ' : ', ord(s[i]):3);
  writeln;
end.

#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

int main()
{
  string s;

  getline(cin, s);
  cout << endl;
  for(unsigned i = 0; i < s.length(); i++)
    cout << s[i] << ": "
         << setw(3) << (int)s[i] << endl;
  cout << endl;
  return 0;
}

Dim s As String, i As Integer

Input s
Print
For i = 1 To Len (s)
  Print Using "! : ###";Mid(s, i, 1);Asc(Mid(s, i, 1))
Next
Print
End

s = input()
print()
for i in range(len(s)):
    print("%s : %3d" % (s[i], ord(s[i])))
print()

s = input()
print()
for i in s: # i-kolejne znaki w s
    print("%s : %3d" % (i, ord(i)))
print()

Aligator Arek

A :  65
l : 108
i : 105
g : 103
a :  97
t : 116
o : 111
r : 114
  :  32
A :  65
r : 114
e : 101
k : 107

Często zdarza się, iż chcemy połączyć dwa lub więcej tekstów w jeden tekst. Operacja łączenia tekstu nosi nazwę konkatencji (ang. concatenation). W przypadku łańcuchów jest to bardzo proste:

s3 := s1+s2;

s3 = s1+s2;

s3 = s1+s2

s3 = s1+s2

Podmiana znaku w łańcuchu jest operacją prostą. Po prostu odwołujemy się do wybranego elementu w zmiennej łańcuchowej – może nią być również tablica znaków – i zapisujemy go nową zawartością:

s[i] := 'znak';
s[i] := char(kod);

s[i] = 'znak';
s[i] = kod

Mid(s, i, 1) = "znak"
Mid(s, i, 1) = Chr(kod)

s = s[:i]+"znak"+s[i+1:]
s = s[:i]+chr(kod)+s[i+1:]

Wstawienie znaku wymaga przesunięcia części znaków w zmiennej łańcuchowej, aby udostępnić miejsce na wstawiany znak. Operacja wstawiania znaku lub łańcucha znaków jest obsługiwana przez funkcje biblioteczne:

insert(s1, s2, i);

s2.insert(i, s1);

s2 = Left(s2, i-1)+s1+Right(s2, Len(s2)-i+1)

s2 = s2[:i]+s1+s2[i:]

Język FreeBasic nie posiada bezpośredniej funkcji wstawiania znaku lub łańcucha do innego łańcucha. Dlatego posiłkujemy się dwoma funkcjami pomocniczymi:

Przykładowe programy

program prg;

var
  s : ansistring;
begin
  s := 'Rudy lisek';
  writeln(s);
  insert (', szybki', s, 5);
  writeln(s);
  writeln;
end.

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;

  s = "Rudy lisek";
  cout << s << endl;
  s.insert(4, ", szybki");
  cout << s << endl << endl;
  return 0;
}

Dim s As String

s = "Rudy lisek"
Print s
s = Left(s, 4)+", szybki"+Right(s, 6)
Print s
Print
End

s = "Rudy lisek"
print(s)
s = s[:4]+", szybki"+s[4:]
print(s)
print()

Rudy lisek
Rudy, szybki lisek

Usunięcie znaku z łańcucha/tablicy polega na przesunięciu wszystkich znaków następujących za znakiem usuwanym o jedną pozycję w lewo. W ten sposób znak zostaje nadpisany znakiem sąsiadującym z prawej strony – w efekcie zniknie on z łańcucha. Dla łańcuchów znakowych mamy w każdym z wybranych języków programowania gotowe funkcje usuwania znaku lub fragmentu łańcucha.

delete(s, i, n);

s.erase(i, n);

s = Left(s, i-1)+Right(s, Len(s)-i-n+1)

s = s[:i]+s[i+n:]

Przykładowe programy

program prg;

var
  s : ansistring;
begin
  s := 'Rakieta kosmiczna';
  writeln(s);
  delete(s, 11, 1);
  writeln(s);
  writeln;
end.

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;

  s = "Rakieta kosmiczna";
  cout << s << endl;
  s.erase(10, 1);
  cout << s << endl << endl;
  return 0;
}

Dim s As String

s = "Rakieta kosmiczna"
Print s
s = Left(s, 10)+Right(s, 6)
Print s End

s = "Rakieta kosmiczna"
print(s)
s = s[:10]+s[11:]
print(s)

Rakieta kosmiczna
Rakieta komiczna

Zastępując fragment łańcucha innym łańcuchem możemy wykorzystać funkcje usuwania i wstawiania tekstu – najpierw usuwamy zastępowany fragment z łańcucha, a następnie wstawiamy na jego miejsce nowy fragment. W języku C++ możemy wykorzystać funkcję składową replace( ) klasy string, która wykonuje dokładnie to samo zadanie. W języku FreeBasic wykorzystujemy funkcje Left( ) i Right( ).

delete(s2, i, n);
insert(s1, s2, i);

s2.replace(i, n, s1);

s2 = Left(s2, i-1)+s1+Right(s2, Len(s2)-i-n+1)

s2 = s2[:i]+s1+s2[i+n:]

Przykładowe programy

program prg;

var
  s : ansistring;
begin
  s := 'Zielone, stare drzewko';
  writeln(s);
  delete(s, 10, 5);
  insert('wysokie', s, 10);
  writeln(s);
  writeln;
end.

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;

  s = "Zielone, stare drzewko";
  cout << s << endl;
  s.replace(9, 5, "wysokie");
  cout << s << endl << endl;
  return 0;
}

Dim s As String

s = "Zielone, stare drzewko"
Print s
s = Left(s, 9)+"wysokie"+Right(s, 8)
Print s
End

s = "Zielone, stare drzewko"
print(s)
s = s[:9]+"wysokie"+s[14:]
print(s)

Zielone, stare drzewko
Zielone, wysokie drzewko

Łańcuchy tekstowe możemy porównywać przy pomocy typowych operatorów porównań. Jednakże obowiązuje tutaj kilka zasad.

Dwa łańcuchy są równe, jeśli składają się z takiej samej liczby znaków oraz zgadzają się ze sobą na każdej pozycji znakowej.

Jeśli dwa łańcuchy mają różną długość, lecz krótszy łańcuch zawiera te same początkowe znaki co łańcuch dłuższy, to krótszy jest mniejszy, a dłuższy jest większy.

W dwóch łańcuchach porównywane są znaki na odpowiadających sobie pozycjach znakowych aż do napotkania niezgodności kodów. Wtedy mniejszy łańcuch jest tym, który posiada na porównywanej pozycji znak o mniejszym kodzie. Na przykład:

"ALA" > "AKACJA" – kod literki L jest większy od kodu literki K.

Taki sposób porównywania nosi nazwę leksykograficznego. Zwróć uwagę, iż w ten sposób nie można porównywać łańcuchów zawierających polskie litery – poprawny będzie jedynie test na równość łańcuchów.

W poniższej tabelce zebraliśmy często wykonywane, typowe operacje na tekstach. Z operacji tych będziemy intensywnie korzystać w przykładach programowych do omawianych algorytmów tekstowych.

readlns);
write('opis'); readln(s) 

writeln(s);
write(s);

if s = '' then …
if length(s) = 0 then …

s2 = copy(s1, i, n);

s2 = copy(s1, 1, n);

s2 = copy(s1, length(s1)-n+1, n);

getline(cin, s);
cout << "opis"; getline(cin, s)

cout << s << endl;
cout << s;

if(s == "") …
if(!s.length())…
if(!s.size())…

s2 = s1.substr(i, n);

s2 = s1.substr(0, n);

s2 = s1.substr(s1.length()-n);

Line Input s
Line Input "opis";s

Print s
Print s;

If s = "" Then …
If Len(s) = 0 Then …

s2 = Mid(s1, i, n)

s2 = Left(s1, n)

s2 = Right(s1, n)

s = input()
s = input("opis")

print(s)
print(s, end="")

if s == "": …
if not s: …

s2 = s1[i:i+n]

s2 = s1[:n]

s2 = s1[-n:]