Anagramy

powrót

Anagram to wyraz lub zdanie powstałe po przestawieniu liter innego wyrazu (zdania). Oba wyrazy składają się z tej samej puli znaków, tylko w innym porządku. 

Kilka przykładów:

$$adam$$ $$dama$$

$$fraktal$$ $$kartafl$$

Żeby sprawdzić, czy dwa słowa są anagramami policzymy wystąpienia każdej litery z pierwszego słowa, a następnie będziemy odejmować wystąpienia liter z drugiego słowa. Jeśli liczniki zostaną wyzerowane, oznaczać to będzie, że podane słowa są anagramami.

Jeśli będzie taka sytuacja, że ciągi znaków są różnej długości, to możemy od razu stwierdzić, że to nie są anagramy.

Przykład

Przeanalizujemy pierwszy przykład. Wystąpienia liter w słowie $$adam$$:

a - 2

d - 1

m - 1

Kody ASCII powyższych liter to: 

a - 97

d - 100

m - 109

a więc wartości komórek tablicy licz[97] = 2, licz[100] = 1, licz[109] = 1 (tablica licz[127] jest zadeklarowana i wyzerowana w poniższym programie, służy do zliczania liter). 

Teraz robimy odwrotnie w stosunku do drugiego słowa. Każde wystąpienie litery dekrementujemy (zmniejszamy o 1). Jeśli w rezultacie wszystkie komórki tablicy będą równe zero, oznaczać to będzie, że wystąpienie każdej litery w jednym i drugim wyrazie jest takie samo.

Implementacja algorytmu

//www.algorytm.edu.pl
#include<iostream>
#include<cstring>
using namespace std;
 
bool czy_anagram(char *a, char *b)
{
	//wyznaczenie liczby liter w slowie a i w slowie b
  	int dl1 = strlen(a), dl2 = strlen(b);
  	//jesli dlugosci wyrazów nie sa równe, to nie moga
  	//byc anagramy
	if(dl1!=dl2)return false;
  
  	int licz[127]={}; //zerujemy licznniki
  	for(int i=0;i<dl1;i++)
  		licz[a[i]]++; //zliczamy litery pierwszego wyrazu
  	for(int i=0;i<dl1;i++)
  		licz[b[i]]--; //odejmowanie wystapien liter
  		
  	for(int i=0;i<127;i++)
  		if(licz[i]!=0) //jesli ktorys licznik sie nie wyzerowal
			return false; //to oznacza, ze słowa nie sa anagramami
		
  return true; //jesli wszystkie liczniki sie wyzerowały, to mamy anagramy
} 
 
int main()
{
 
   char a[101], b[101]; //dwa słowa, maksymalnie 100 znaków
   cout<<"Podaj dwa wyrazy: ";
   cin>>a>>b;
 
   if(czy_anagram(a,b))
     cout<<"Podane wyrazy sa anagramami\n";
   else
     cout<<"Podane wyrazy nie są anagramami\n";
 

    return 0;
}