Teraz ja, teraz ja!
#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
typedef std::unordered_map<char, int> intersection_map;
intersection_map string_intersection(std::string s1, std::string s2) {
std::sort(s1.begin(), s1.end());
std::sort(s2.begin(), s2.end());
std::string result(std::min(s1.length(), s2.length()), ' ');
std::string::iterator pos = std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
result.begin());
result.erase(pos, result.end());
intersection_map result_map;
for (char c : result) {
result_map[c]++;
}
return result_map;
}
int main() {
std::string s1("ala ma kota kota ma ala");
std::string s2("janek tez ma kota i raka");
intersection_map result = string_intersection(s1, s2);
for (auto pair : result) {
std::cout << pair.first << "-" << pair.second << std::endl;
}
return 0;
}
Złożoność - dwa sorty, trzy iteracje i jeszcze hash mapa! (3.2 GHz, -O2, gcc 4.6.1, 1000000x = 1.26 sekundy, chociaż to jest pewnie niemiarodajne)
Wynik dla tych danych z kodu:
-5
a-5
k-2
m-1
o-1
t-2
Wynik jest inny niż w kodzie wyżej, ponieważ robię część wspólną. I tak nie wiadomo o co chodziło autorowi. :-)
A tutaj taki na wzór ŁF:
std::string string_intersection2(std::string s1, std::string s2) {
std::string result;
result.reserve(std::min(s1.length(), s2.length()));
// tu sobie mozna zmieniac :-P
const char start_char = 0;
const char stop_char = 127;
std::vector<int> char_lut(stop_char - start_char + 1, 0);
for (char c : s1) {
char_lut[c - start_char] = 1;
}
for (char c : s2) {
const char index = c - start_char;
if (char_lut[index] == 1) {
char_lut[index] = 2;
result += c;
}
}
return result;
}
Haha, zabawa nie ma końca. Tutaj taki na wzór ŁF, który liczy jak mój pierwszy i jest szybszy ale nie tak wygodny:
std::vector<int> string_intersection3(std::string s1, std::string s2) {
const char start_char = 0;
const char stop_char = 127;
const size_t count = stop_char - start_char + 1;
std::vector<int> char_hist1(count + 1, 0);
std::vector<int> char_hist2(count + 1, 0);
for (char c : s1) {
char_hist1[c - start_char]++;
}
for (char c : s2) {
char_hist2[c - start_char]++;
}
std::vector<int> result(count + 1, 0);
for (size_t i = 0; i < count; ++i) {
if (char_hist1[i] > 0 && char_hist2[i] > 0) {
result[i] = std::min(char_hist1[i], char_hist2[i]);
}
}
return result;
}
Do wyboru do koloru w 3 językach. :-)