[TEMÃ] Determinare anagrame

Salut. Se dă un şir de caractere ce conţine cuvinte formate din litere mici ale alfabetului englez, separate prin unul sau mai multe spații. Să se determine câte cuvinte din sir sunt anagrame ale ultimului cuvânt, fără a fi identice cu acesta.

Exemplu:

Intrare said:

Iesire said:

Ce am făcut arată cam aşa:

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef char matrice_cuvinte[100][30];

int determinare_anagrame(matrice_cuvinte matrice, int numar_cuvinte)
{
	int suma = 0;
	char copie_ulitimul_cuvant[40];

	strcpy(copie_ulitimul_cuvant, matrice[numar_cuvinte - 1]);

	sort(copie_ulitimul_cuvant, copie_ulitimul_cuvant + strlen(copie_ulitimul_cuvant));

	for (int i = 0; i < numar_cuvinte - 1; i++)
	{
		if (strcmp(matrice[i], matrice[numar_cuvinte - 1]) != 0)   // nu este deja identic cu ultimul cuvant din matrice
		{
			sort(matrice[i], matrice[i] + strlen(matrice[i]));
			suma += (strcmp(matrice[i], copie_ulitimul_cuvant) == 0);
		}
	}

	return suma;
}

void construire_matrice_cuvinte(matrice_cuvinte &matrice, char sir_cuvinte[], int &numar_cuvinte)
{
	numar_cuvinte = 0;

	char *p = strtok(sir_cuvinte, " ");
	while (p != NULL)
	{
		strcpy(matrice[numar_cuvinte++], p);
		p = strtok(NULL, " ");
	}
}

int main(void)
{
	char sir_cuvinte[300];
	matrice_cuvinte matrice;
	int numar_cuvinte;

	cin.get(sir_cuvinte, 255);

	construire_matrice_cuvinte(matrice, sir_cuvinte, numar_cuvinte);

	cout << determinare_anagrame(matrice, numar_cuvinte);

	return 0;
}

Însă primesc 60 puncte (pic un test).

Edited by sftpdt, 23 May 2015 - 07:08.

Felicitari!
Ce test pici?

Scrie doar Raspuns gresit.

eu din codul tau nu reusesc sa inteleg unde determini daca un cuvant este anagrama altui cuvant.

Le sortez pe amândouă şi verific dacă sunt identice.

int determinare_anagrame(matrice_cuvinte matrice, int numar_cuvinte)
{
	int suma = 0;

	char copie_ulitimul_cuvant[40];

	strcpy(copie_ulitimul_cuvant, matrice[numar_cuvinte - 1]);

	sort(copie_ulitimul_cuvant, copie_ulitimul_cuvant + strlen(copie_ulitimul_cuvant)); // aici sortez copia ultimului cuvant

	for (int i = 0; i < numar_cuvinte - 1; i++)
	{
		if (strcmp(matrice[i], matrice[numar_cuvinte - 1]) != 0)   // nu este deja identic cu ultimul cuvant din matrice
		{
			sort(matrice[i], matrice[i] + strlen(matrice[i])); // sortez cuvantul actual
			suma += (strcmp(matrice[i], copie_ulitimul_cuvant) == 0); // verific daca sunt identice
		}
	}

	return suma;
}

Edited by sftpdt, 23 May 2015 - 07:31.

aia e functia care iti numara,

return suma

eu vreau doar partea care deterinama daca doua cuvinte sunt anagrame

mai pe romaneste, separa o problema de alta

bool Cuvinte_anagrame(char cuvant1[], char cuvant2[])
{
	char copie1[100], copie2[100];

	strcpy(copie1, cuvant1);
	strcpy(copie2, cuvant2);

	sort(copie1, copie1 + strlen(copie1));
	sort(copie2, copie2 + strlen(copie2));

	return ( strcmp(copie1, copie2) == 0 );
}

Faci prea multe copii inutile. Eu as salva tot inputul intr-un singur string, si intr-un alt array pozitiile inceputurilor cuvintelor (daca cuvintele sunt mereu despartite de un singur caracter) inca din timpul citirii.

Pentru claritatea algoritmului, as salva si pozitiile ultimelor litere ale tuturor cuvintelor intr-un alt array.

Dupa ce am scanat ultimul cuvant, stiu exact unde sa sar in interiorul acestui string citit si ce caractere sa compar cu care caractere.

Totul manual, fara functii.

Daca vrei ceva mai avansat, te poti gandi la un algoritm de hashing bazat pe numere prime. Nu ar trebui sa ai coliziuni. Nu e un algoritm neaparat mai eficient, doar mai provocator dpv intelectual.

Daca vrei si mai avansat, te poti inspira de aici: https://github.com/s...aster/bitgram.c

Edited by OriginalCopy, 23 May 2015 - 10:38.

De ce nu folosesti std::string?

OriginalCopy, on 23 mai 2015 - 09:47, said:

Mai fac copii deoarece nu se ştie când mai am nevoie de respectiva variabilă.. Mersi de sfat .

Se pare că nu luam 100p din cauza dimensiunilor tablourilor. Le-am mai mărit şi e ok.

dani.user, on 23 mai 2015 - 11:03, said:

Să mai exersez cu char*. Am anul viitor bacalaureatul şi nu cred că am voie cu string (sau vector/map/algorithm/etc) ... din comoditatea multor profesori cărora le este lene să înveţe lucruri noi şi se bazează pe aceeaşi materie.

Citind codul tau ma tot intreb ce-i matricea de cuvinte. Mai degraba e un vector de cuvinte.
Rezolvarea mi se pare mult mai eleganta urmand niste pasi simpli:

• Spargerea propozitiei in cuvinte
  
• Iterarea prin toate cuvintele mai putin ultimul
  
• Verificarea relatiei de anagrama intre fiecare cuvant si ultimul

#include <iostream>
#include <sstream>
#include <vector>
#include <cstring>

using namespace std;

bool isAnagram(const string& first, const string& second)
{
   if ((first == second) || (first.size() != second.size()))
   {
	  return false;
   }
   int letterOccurences[256] = {0};
   int reference[256] = {0};
   for (auto& c : first) {
	  ++letterOccurences[c];
   }
   for (auto& c : second) {
	  --letterOccurences[c];
   }
   return memcmp(letterOccurences, reference, sizeof(reference)) == 0;
}

vector<string> getWords(const string& sentence)
{
   vector<string> result;
   istringstream stream(sentence);
   string word;
   while (getline(stream, word, ' ')) {
	  result.push_back(word);
   }
   return result;
}

int count_anagrams_of_last_word(const string& sentence)
{
   int result = 0;
   auto words = getWords(sentence);
   auto& lastWord = words[words.size() - 1];

   for (int i = 0; i < words.size() - 1; i++) {
	  if (isAnagram(words[i], lastWord)) {
		 ++result;
	  }
   }

   return result;
}

int main()
{
   cout << count_anagrams_of_last_word("arc ingrat din granit car argint arc rating rac argint") << endl;
   return 0;
}

sftpdt, on 23 mai 2015 - 11:11, said:

Cu solutia mea, nu ai fi avut tablouri in primul rand.

Complexitatea algoritmului e aceeasi, insa copierea de date insasi costa si ea.