[C] anagram

misiekprezes · Post autor: **misiekprezes** » 10 gru 2009, o 20:17

Dwa wyrazy nazywamy anagramami jesli drugi mozna otrzymac
z pierwszego przez przestawienie kolejnosci liter, na przykład „kanonada”
i „anakonda”, „sekret” i „kretes”. Napisz funkcje która sprawdza, czy dane dwa
łancuchy sa anagramami. Oszacuj jej złozonosc obliczeniowa.
moze ktoś pomóc?!

kadiii · Post autor: **kadiii** » 10 gru 2009, o 21:11

Chwilka szukania i . Google naprawdę nie gryzie, przynajmniej u nas w Polsce

matshadow · Post autor: **matshadow** » 10 gru 2009, o 21:15

sortowanie leksykograficzne. Napisz sobie funkcję, która posortuje Ci tablicę znaków (w C++ jest już gotowa ). Jeśli posortowane tablice obu słów mają identyczną zawartość, to oba słowa to anagramy.
Ew. możesz napisać (będzie łatwiej) dla każdego ze słów.

misiekprezes · Post autor: **misiekprezes** » 10 gru 2009, o 21:18

hmm jak?!

kadiii · Post autor: **kadiii** » 10 gru 2009, o 21:28

Masz stały, dość mały alfabet wejściowy, więć możesz posortować w liniowej złożoności tablicę znaków - zwiększająć przy każdej literce wartość tablicy o indeksie kodu ascii tej literki (pomniejszonym o jakąś stałą tak żeby a wyszło jako tab[0]). Potem porównujesz literka po literce i masz wynik czy jest anagramem czy nie.

Kod: Zaznacz cały

int k=0;
for(i=0;i<slowo.length();i++)
 tab[slowo[i]-97]++;
for(i=0;i<25;i++)
 if(tab[i]!=0)
  for(j=0;j<tab[i];j++)
   slowo[k++]=i+97;

qwertyhnmju · Post autor: **qwertyhnmju** » 30 gru 2009, o 13:35

Hej. Podepnę się pod temat.
Mam podobny problem z tym, że mam do porównania 2 tablice 1-wymiarowe.
W jaki sposób wypadałoby to zapisać w schemacie? Najpierw posortować jedną, później drugą i porównać?? Tylko w jaki sposób? Jestem już kompletnie zielony... A później jeszcze do C, ale myślę, że z tym byłoby trochę łatwiej.

szatkus · Post autor: **szatkus** » 30 gru 2009, o 13:42

Kod: Zaznacz cały

equal=1
for (i=0; i<n;i++) 
   if (t[i] != t2[i]) equal = 0

Tak mniej więcej wygląda zapis tego w C. Zmienna n to długość tablic, a equal oznacza czy są równe czy nie.