Algorytmy na tekstach: czy palindrom, czy anagram?
Poniżej omówimy przykładowe algorytmy działające na danych tekstowych zapisanych w postaci łańcucha znaków string. Algorytmy sprawdzają czy podany ciąg znaków jest palindromem oraz czy dwie wartości tekstowe są anagramem.
Palindrom, to wyrażenie tekstowe, które czytane od lewej do prawej lub od prawej do lewej brzmi tak samo. Przykładem prostego palindromu jest imię ALA. Gdy podany ciąg znaków czytamy od lewej do prawej lub na odwrót to brzmi tak samo.
Anagram, to wyrażenie tekstowe, które powstało z przestawienia liter w wyrażeniu pierwotnym przy wykorzystaniu wszystkich znaków wyrażenie pierwotnego. Przykładem anagramu jest słowo krab, które mogło powstać z przestawienia liter w słowie bark.
Oba podane algorytmy są doskonałym ćwiczeniem utrwalającym posługiwanie się tablicami. W obu algorytmach wykorzystano pozycję znaku w kodzie ASCII. Dostęp do pojedynczego znaku podanych wyrażeń łańcuchowych (typ string) odbywa się na tej samej zasadzie co odczyt elementu w tablicy.
Algorytm sprawdzający czy podany ciąg znaków jest palindromem
Algorytm sprawdzający czy dany ciąg znaków tworzy palindrom działa w pojedynczej pętli, która porównuje kolejno odczytane znaki z indeksów stojących z lewej jak i z prawej strony. Jeżeli odczytane znaki z podanych indeksów się nie zgadzają, to wyrażenie nie jest palindromem.
Schemat algorytmu sprawdzającego czy ciąg znaków jest palindromem
Przykładowy kod funkcji zapisanej w C#, który sprawdza czy podany ciąg znaków jest palindromem.
Wskazówka:
bool czyPalindrom(string slowo)
{
//ustaw poczatek i koniec granicy przegladania
//znaków w słowie z lewej i prawej strony
int L = 0, P = slowo.Length - 1;
while (L<P)
{
//jak sie znaki nie zgadzają to zakańcz,
//bo słowo nie jest palindromem
if (slowo[L] != slowo[P]) return false;
L++;
P--;
}
return true;
}
Uwaga: Kod algorytmu nie sprawdza czy kolejne znaki są zapisane z dużej czy z małej litery. Zamiana na duże litery została ustawiona w kontrolce TextBox we właściwości CharacterCasing na Upper. Patrz poniższa ilustracja
Algorytm sprawdzający czy podany ciąg znaków jest anagramem
Aby sprawdzić czy mamy do czynienia z anagramem musimy podać dwie wartości ciągu znaków. Jeden z ciągów znaków jest ciągiem wyjściowym, a drugi ciągiem zmodyfikowanym, zawierający znaki z ciągu wejściowego.
Sprawdzanie czy ciągi tworzą anagram polega na sprawdzeniu dwóch warunków. Pierwszy warunek długości obu ciągów musza być jednakowe. Drugi warunek to suma wystąpień pojedynczych znaków w pierwszym ciągu jest jednakowa z sumą wystąpień pojedynczych znaków w drugim ciągu.
Podane rozwiązanie bazuje na pomyśle indeksowania znaków w tablicy sum zgodnie z indeksem znaku w kodzie ASCII. Przykładowo znak duża litera A ma pozycję 65, więc każde wystąpienie znaku A w słowie wyjściowym będzie zliczane w tablicy sum dla indeksu 65.
Analiza drugiego słowa (czyli anagramu) polega na tym, ze gdy wystąpi na przykład znak A, to w tablicy sum w indeksie 65 będzie odejmowane każde pojedyncze wystąpienie znaku A. Sprawdzenie czy mamy do czynienia z anagramem, to przeglądnięci tablicy sum czy na każdym indeksie suma wynosi zero. Jeżeli tak, to mamy do czynienia z anagramem.
Schemat algorytmu sprawdzającego czy ciągi znaków tworzą anagram
Przykładowy kod funkcji zapisany w C# sprawdzający czy mamy do czynienia z anagramem
Wskazówka:
bool czyAnagram(string slowo1, string slowo2)
{
//jezeli długości słów sa rózne to
//nie słowa nie są anagramami
if (slowo1.Length != slowo2.Length) return false;
//algorytm działa wykorzystując pozycję
//znaków w kodzie ASCII, wszystkich jest 256
//utwórz tablice dla sum występowania indeksów znaków
int[] tabSum = new int[256];
//zeruj sumy
for (int i = 0; i < 256; i++)tabSum[i]=0;
//sumuj wystąpienie znaków w pierwszym slowie
for (int i = 0; i < slowo1.Length; i++) tabSum[slowo1[i]]++;
//odejmi wystapienie znaku gdy wystapi w drugim slowie
for (int i = 0; i < slowo2.Length; i++) tabSum[slowo2[i]]--;
//sprawdx czy sie wyzerowały wystąpienia,
//jezeli nie, to słowa nie są anagramami
for(int i=0; i < 256; i++)
if(tabSum[i]!=0) return false;
return true;
}
Proponowany układ kontrolek użytych w formatce aplikacji desktopowej wygląda jak poniżej. Obie kontrolki TextBox mają ustawioną właściwość CharacterCasing na Upper.
Przykładowa aplikacja wykorzystująca oba algorytmy sprawdzające czy mamy do czynienia z palindromem lub anagramem.
Pełny kod aplikacji zapisanej w VS C#
Wskazówka:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace _21AlgPalindromAnagram
{
public partial class Form1 : Form
{
bool czyPalindrom(string slowo)
{
//ustaw poczatek i koniec granicy przegladania
//znaków w słowie z lewej i prawej strony
int L = 0, P = slowo.Length - 1;
while (L<P)
{
//jak sie znaki nie zgadzają to zakańcz,
//bo słowo nie jest palindromem
if (slowo[L] != slowo[P]) return false;
L++;
P--;
}
return true;
}
bool czyAnagram(string slowo1, string slowo2)
{
//jezeli długości słów sa rózne to
//nie słowa nie są anagramami
if (slowo1.Length != slowo2.Length) return false;
//algorytm działa wykorzystując pozycję
//znaków w kodzie ASCII, wszystkich jest 256
//utwórz tablice dla sum występowania indeksów znaków
int[] tabSum = new int[256];
//zeruj sumy
for (int i = 0; i < 256; i++)tabSum[i]=0;
//sumuj wystąpienie znaków w pierwszym slowie
for (int i = 0; i < slowo1.Length; i++) tabSum[slowo1[i]]++;
//odejmi wystapienie znaku gdy wystapi w drugim slowie
for (int i = 0; i < slowo2.Length; i++) tabSum[slowo2[i]]--;
//sprawdx czy sie wyzerowały wystąpienia,
//jezeli nie, to słowa nie są anagramami
for(int i=0; i < 256; i++)
if(tabSum[i]!=0) return false;
return true;
}
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
if (textBox1.Text.Length < 1) return;
if (czyPalindrom(textBox1.Text))
MessageBox.Show(
"Podane słowo jest palindromem",
"Czy palindrom?",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
else MessageBox.Show(
"Podane słowo nie jest palindromem",
"Czy palindrom?",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
private void button2_Click(object sender, EventArgs e)
{
if (textBox1.Text.Length < 1 || textBox2.Text.Length < 1) return;
if (czyAnagram(textBox1.Text, textBox2.Text))
MessageBox.Show(
"Podane słowa są anagramami",
"Czy anagram?",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
else MessageBox.Show(
"Podane słowa nie są anagramami",
"Czy anagram?",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
}
}
