とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

高速アナグラムプログラム - マルチマップの使用

STL―標準テンプレートライブラリによるC++プログラミング 第2版
単語辞書 を調べ,一番大きいアナグラムグループから出力するプログラム改。
改行とコメント入れてみた。コメントが間違ってるかもしれない。こいつは信用ならないぜ。

// P240 ex15-01.cpp
#pragma warning(disable:4503) // MSVC9.0 のうるさい警告止め
#include<iostream>
#include<string>
#include<fstream>
#include<iterator>
#include<map>
#include<algorithm>
#include<list>
#include<functional>

int main(){
 using std::cout;
 using std::flush;
 using std::string;
 using std::cin;
 using std::ifstream;
 using std::endl;
 using std::istream_iterator;
 using std::multimap;
 using std::sort;
 using std::map;
 using std::list;
 using std::greater;
 using std::pair;
 using std::adjacent_find;
 using std::not2;
 using std::find_if;
 using std::bind1st;
 using std::distance;

 cout << "Anagram group finding program:\n"
  "finds all anagram groups in a dictionary.\n\n"
  "First, enter the name of the file containing\n"
  "the dictionary: " << flush;
 string dictionaryName;
 cin >> dictionaryName;
 ifstream ifs(dictionaryName.c_str());
 if(!ifs.is_open()){
  cout << "Eh? Could not open file named " << dictionaryName << endl;
  return 1;
 }

 // データをmultimapにつっこむ
 cout << "\nReading the dictionary ..." << flush;
 typedef multimap<string, string> Multimap;
 typedef Multimap::value_type PS;
 Multimap wordPairs;
 for(istream_iterator<string> iter(ifs), end; iter != end; ++iter){
  string word = *iter;
  sort(word.begin(), word.end());
  wordPairs.insert(PS(word, *iter));
 }

 cout << "\nSearching " << wordPairs.size() <<
  " words for anagram groups..." << flush;

 // multimapからmapへ
 // mapはアナグラムのサイズをキーにしたlistをもつ
 // そのlistはアナグラムグループ(イテレータ範囲)
 typedef Multimap::const_iterator PSi;
 typedef pair<PSi, PSi> PPS;
 typedef map<int, list<PPS>, greater<int> > Map;
 Map groups;
 cout << "\n\nThe anagram groups are: " << endl;
 for(PSi j = wordPairs.begin(), end = wordPairs.end(), k;;){
  // == (正確には>=)の範囲 (j, k] を探す
  j = adjacent_find(j, end, not2(wordPairs.value_comp()));
  if(j == end)break;
  k = find_if(j, end, bind1st(wordPairs.value_comp(), *j));
  Multimap::size_type n = distance(j, k);
  if(n > 1){
   groups[n].push_back(PPS(j, k));
   j = k;
  }
 }

 for(Map::const_iterator m = groups.begin(), end = groups.end();
  m != end; ++m){
   cout << "Anagram groups of size " << m->first << ":\n";
   // アナグラムグループ (l->first, l->second] を表示
   for(list<PPS>::const_iterator l = m->second.begin(), end = m->second.end();
    l != end; ++l)
   {
    cout << "  ";
    PSi j = l->first, k = l->second;
    for(;j != k; ++j)cout << j->second << " ";
    cout << endl;
   }
 }
}