anagramy spoj

Question

Witam. Robię zadanie ze spoj'a, niestety dość nieudolnie.

http://pl.spoj.com/problems/AL_30_01/

1 przypadek błędna odpowiedź, chociaż dla wymyślonych przeze mnie przypadków działa, więc 1 pytanie czy podane rozwiązanie jest poprawne?

https://ideone.com/gsj2hG kod.

Uznałem, że jest błędne, dlatego napisałem inną wersję z użyciem sortowania bąbelkowego stringów. Przy drugiej jest przekroczony limit czasu, a czasami " Błędna odpowiedź ". To rozwiązanie też jest błędne czy zwyczajnie sortowanie zajmuje za dużo czasu?

https://ideone.com/669AEy 2 kod.

Z góry dziękuję za pomoc.

Comments

Dla 1 sprawdź taki test:

Wejście:
hibdzioo 1
chibdzio

Wychodzi 1, a powinno 0.

Answer 1

Masz błąd w sortowaniu bąbelkowym. Iterator 'i' nie musi mieć ograniczenia w postaci wyraz.length()-1. Przez to nie sprawdzasz ostatniej litery. Dodatkowo można by sortować anagram tylko raz, a nie tyle razy ile jest testów do sprawdzenia:

#include <iostream>
#include <string>
using namespace std;

void sortowaniebabelkowe(string &wyraz)
{

	for (int i = 0; i<wyraz.length() ; i++)
	{
		for (int j = 0; j<wyraz.length() - 1; j++)
		{
			if (int(wyraz[j])>int(wyraz[j + 1]))

				swap(wyraz[j], wyraz[j + 1]);
		}
	}
}

int main()
{
	string anagram;
	int n;
	int licznik = 0;
	cin >> anagram;
	cin >> n;
	sortowaniebabelkowe(anagram);

	for (int i = 0; i<n; i++)
	{
		string czyanagram;
		cin >> czyanagram;
		if (anagram.length() == czyanagram.length())
		{
			sortowaniebabelkowe(czyanagram);
			if (anagram == czyanagram)
				licznik++;
		}
	}
	cout << licznik;
}

Mi taki kod zaliczyło na granicy poprawności (0.97s, a limit jest 1s). Mógłbyś zamiast sortowania bąbelkowego użyć funkcji sort:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	string anagram;
	int n;
	int licznik = 0;
	cin >> anagram >> n;
	sort(anagram.begin(), anagram.end());

	for (int i = 0; i<n; i++)
	{
		string czyanagram;
		cin >> czyanagram;
		if (anagram.length() == czyanagram.length())
		{
			sort(czyanagram.begin(), czyanagram.end());
			if (anagram == czyanagram)
				licznik++;
		}
	}
	cout << licznik;
}

[EDIT]: Można też użyć funkcji is_permutation:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	string anagram;
	int n;
	int licznik = 0;
	cin >> anagram >> n;

	for (int i = 0; i<n; i++)
	{
		string czyanagram;
		cin >> czyanagram;
		if (anagram.length() == czyanagram.length())
			if (is_permutation(anagram.begin(), anagram.end(), czyanagram.begin())) 
				licznik++;
	}
	cout << licznik;
}

Answer 2

To nie jest dobra droga rozwiązania. Zlicz wystąpienia znaków w obu stringach (wzorzec i kandydat na anagram). Jeśli są równe, to jest to anagram;)

Comments

Można prosić o jakiś przykład w nowoczesnym C++?

---

A proszę...

Czas 0.04 pamięć 16M

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
 
std::unordered_map<char, short unsigned> make_map(const std::string& msg) {
    std::unordered_map<char, short unsigned> msg_map;
    for(const char& ch: msg) {
        msg_map[ch] += 1;
    }
    return msg_map;
}
 
int main() {
    size_t counter;
    std::string message, anagram_candidate;
    std::cin >> message >> counter;
    auto message_map{make_map(message)};
    size_t anagram_counter{};
    while(counter-->0) {
        std::cin >> anagram_candidate;
        message_map == make_map(anagram_candidate) && anagram_counter++;
    }
    
    std::cout << anagram_counter;
}

Po optymalizacji i zrezygnowaniu z wysokopoziomowych konstrukcji

Czas wykonania 0.00 pamięć 2.7M

#include <cstdio>
#include <cstring>
 
static const size_t table_size = 'z' - 'a' + 1;
 
void count_chars(const char * msg, size_t size, unsigned short * chars_counted) {
    std::memset(chars_counted, 0, table_size * sizeof(unsigned short));
    while(size-->0) {
        chars_counted[msg[size] - 'a']++;
    }
}
 
int main() {
    char msg[1001];
    char anagram_candidate[1001];
    unsigned short msg_table[table_size];
    unsigned short candidate_table[table_size];
    unsigned counter;
    unsigned anagram_counter = 0;
 
    std::scanf("%1000s %u", msg, &counter);
    const size_t msg_len = std::strlen(msg);
    count_chars(msg, msg_len, msg_table);
 
 
    while(counter-->0) {
        std::scanf("%1000s", anagram_candidate);
        count_chars(anagram_candidate, std::strlen(anagram_candidate), candidate_table);
        if(std::memcmp(candidate_table, msg_table, table_size) == 0) {
            anagram_counter++;
        }
    }
    std::printf("%u", anagram_counter);
}

 

---

Dziękuję!