Efektem działania dwóch pierwszych pętli jest utworzenie reprezentacji zbioru liter występujących w słowie
Y w postaci tak zwanego „wektora charakterystycznego”. Dokładniej, po
pętli
dla i = 1,2,…,
d wykonuj lit ← Y[i]
Czyjest[kod(lit)] ← prawda
zachodzi warunek:
Czyjest[
i] = prawda, gdy litera o kodzie i występuje w słowie
Y, oraz
Czyjest[
i] = fałsz — w przeciwnym wypadku. W ostatniej pętli
czyp ← prawda
dla i = 1,2,…,
d wykonuj lit ← X[i]
czyp ← czyp i Czyjest[kod(lit)]
sprawdzamy, czy w słowie
X występuje litera, której nie ma w
Y. Dokładniej, zmiennej
czyp
nadajemy wartość koniunkcji zdań: „czy
i-ta litera słowa
X występuje w
Y”. Tak więc po zakończeniu tej pętli
czyp ma wartość „prawda” dokładnie wtedy, gdy słowo
X jest podrzędne
względem
Y.
Specyfikacja algorytmu A wygląda więc następująco:
Specyfikacja
Dane:
X, Y — słowa, w których występują tylko litery ze zbioru {A, B, C, D, E, F, G, H, I, J}
Wynik:
1 — gdy X jest słowem podrzędnym względem Y,
0 — gdy X nie jest słowem podrzędnym względem Y.
Tabelkę podaną w treści zadania możemy wówczas uzupełnić w oparciu o to, czy X jest podrzędne względem Y:
|
X
|
Y
|
wynik algorytmu A
|
|
HHGGFFEEDDCCBBAA
|
ABCDEFGH
|
1
|
|
DCBADCBA
|
FGHABCJD
|
1
|
|
ABCDE
|
ABCCBA
|
0
|
|
AAAAA
|
AA
|
1
|
|
AA
|
AAAAA
|
1
|
|
ACEGJ
|
ABCDEFGH
|
0
|