srm452

とても久しぶりに参加。

div1:250 NotTwo

最大1000*1000の盤面に、ユークリッド距離が丁度2になるような石のペアが存在しないように可能な限り石を置いた時に最大でいくつ置けるか。
整数座標でユークリッド距離が丁度2になるのは上下左右に2マス離れた場合だけ。
なので石を一つ置くと、置けないという制約がかかった場所が新たに最大4つできる。
制約がかかった場所を最小にしたいが、共有出来る制約が最大4である事は明らか。
そのような置き方は、盤面が無限に広がっている場合「斜めにジグザクに置く」「2*2の石を出来るだけ敷き詰める」という二つの置き方が考えられる。
盤面が2*2とかの時を特別扱いしなくて済むので後者でやると楽。

というのは終わってから気づいた話で、system test中とてもひやひやしてました。

passed system test 174.04

div1:500 IOIString

I,O,?の三文字のみからなる最大長さ2500の文字列が与えられる。
?をIまたはOと置き換えると、

I...(n文字)...O...(n文字)...I

のような部分文字列を含む文字列(IOI string)はいくつ出来るか。

IOI stringでない文字列の数はそれほど多くないので、そっちを引くのかなぁと思った程度。

compiled(challengeする事もあろうかと思って)

div1:1000

読んでません。

opened

結果は250で得た174.04のみで、レーティングは1413 -> 1427と微増。
良いなー黄色良いなー。

C++テンプレートメタプログラミングでbrainfuck

フィボナッチや階乗を計算させるような、一つの整数値が結果になるものは書いた事があったのですが、もっと複雑なものを書いてみたくなったので、チューリング完全性の証明もおまけでついてくるbrainfuckインタプリタを書いてみました。

#include <cstdio>

//////////
// List //
//////////
class Null {};

template<class T, class U>
struct List {
  typedef T Head;
  typedef U Tail;
};

////////////
// Length //
////////////
template<class L>
struct Length;

template<>
struct Length<Null> { enum { value = 0 }; };

template<class T, class U>
struct Length<List<T, U> > { enum { value = 1 + Length<U>::value }; };

/////////////
// Reverse //
/////////////
template<class T, class U>
struct ReverseIter;

template<class T>
struct ReverseIter<Null, T> {
  typedef T Result;
};

template<class T, class U, class V>
struct ReverseIter<List<U, V>, T> {
  typedef typename ReverseIter<V, List<U, T> >::Result Result;
};

template<class L>
struct Reverse {
  typedef typename ReverseIter<L, Null>::Result Result;
};

/////////
// Int //
/////////
template<int v>
struct Int { enum { value = v }; };

//////////
// Char //
//////////
template<char c>
struct Char { static const char value = c; };

////////////////
// MakeMemory //
////////////////
template<unsigned int n>
struct MakeMemory {
  typedef List<Int<0>, typename MakeMemory<n - 1>::Result> Result;
};

template<>
struct MakeMemory<0> {
  typedef Null Result;
};

/////////
// Ref //
/////////
template<class T, unsigned int n>
struct Ref {
  enum { value = Ref<typename T::Tail, n - 1>::value };
};

template<class H, class T>
struct Ref<List<H, T>, 0> {
  enum { value = H::value };
};

///////////////
// BrainFuck //
///////////////
template<class PH, class PT, class MH, class MT, class StdOut>
struct BF;

// Finish
template<class PH, class MH, class MT, class StdOut>
struct BF<PH, Null, MH, MT, StdOut> {
  typedef typename Reverse<StdOut>::Result Result;
};

// > command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'>'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'>'>, PH>, PT, List<U, MH>, V, StdOut>::Result Result;
};

// < command
template<class PH, class PT, class U, class V, class MT, class StdOut>
struct BF<PH, List<Char<'<'>, PT>, List<U, V>, MT, StdOut> {
  typedef typename BF<List<Char<'<'>, PH>, PT, V, List<U, MT>, StdOut>::Result Result;
};

// + command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'+'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'+'>, PH>, PT, MH, List<Int<U::value + 1>, V>, StdOut>::Result Result;
};

// - command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'-'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'-'>, PH>, PT, MH, List<Int<U::value - 1>, V>, StdOut>::Result Result;
};

// . command
template<class PH, class PT, class MH, class MT, class StdOut>
struct BF<PH, List<Char<'.'>, PT>, MH, MT, StdOut> {
  typedef typename BF<List<Char<'.'>, PH>, PT, MH, MT, List<Char<MT::Head::value>, StdOut> >::Result Result;
};

// [ command
template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP {
  typedef typename BFOBLOOP<List<typename PT::Head, PH>, typename PT::Tail, MH, MT, StdOut, level>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFOBLOOP<PH, PT, MH, MT, StdOut, 0> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP<PH, List<Char<'['>, PT>, MH, MT, StdOut, level> {
  typedef typename BFOBLOOP<List<Char<'['>, PH>, PT, MH, MT, StdOut, level + 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP<PH, List<Char<']'>, PT>, MH, MT, StdOut, level> {
  typedef typename BFOBLOOP<List<Char<']'>, PH>, PT, MH, MT, StdOut, level - 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, bool jump>
struct BFOB {
  typedef typename BFOBLOOP<PH, PT, MH, MT, StdOut, 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFOB<PH, PT, MH, MT, StdOut, false> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'['>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BFOB<List<Char<'['>, PH>, PT, MH, List<U, V>, StdOut, U::value == 0>::Result Result;
};

// ] command
template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP {
  typedef typename BFCBLOOP<typename PH::Tail, List<typename PH::Head, PT>, MH, MT, StdOut, level>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFCBLOOP<PH, PT, MH, MT, StdOut, 0> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP<List<Char<']'>, PH>, PT, MH, MT, StdOut, level> {
  typedef typename BFCBLOOP<PH, List<Char<']'>, PT>, MH, MT, StdOut, level + 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP<List<Char<'['>, PH>, PT, MH, MT, StdOut, level> {
  typedef typename BFCBLOOP<PH, List<Char<'['>, PT>, MH, MT, StdOut, level - 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, bool jump>
struct BFCB {
  typedef typename BFCBLOOP<typename PH::Tail, List<typename PH::Head, PT>, MH, MT, StdOut, 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFCB<PH, PT, MH, MT, StdOut, false> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<']'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BFCB<List<Char<']'>, PH>, PT, MH, List<U, V>, StdOut, U::value != 0>::Result Result;
};

// read other character
template<class PH, class U, class PT, class MH, class MT, class StdOut>
struct BF<PH, List<U, PT>, MH, MT, StdOut> {
  typedef typename BF<List<U, PH>, PT, MH, MT, StdOut>::Result Result;
};

// interface
template<class Program>
struct BrainFuck {
  typedef typename BF<Null, Program, Null, MakeMemory<256>::Result, Null>::Result Result;
};

///////////////
// Execution //
///////////////
typedef List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'['>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'<'>, List<Char<'<'>, List<Char<'<'>, List<Char<'-'>, List<Char<']'>, List<Char<'>'>, List<Char<'.'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'>'>, List<Char<'-'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'<'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'>'>, List<Char<'+'>, List<Char<'.'>, Null > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > HelloWorld;
typedef BrainFuck<HelloWorld>::Result OutPut;

///////////
// Print //
///////////
template<class L>
inline void Print(L l);

template<>
inline void Print(Null l) { printf("\n"); }

template<class T, class U>
inline void Print(List<T, U> l) { printf("%c", T::value); Print(U()); }

int main() {
  Print(OutPut());
  return 0;
}

HelloWorldというのがbrainfuckプログラム本体です。Charの型リストになっています。
インタプリタ本体は

template<class PH, class PT, class MH, class MT, class StdOut>
struct BF;

で、実行しているプログラムとメモリをzipper(kinabaさんの記事参照)で持っています。PHとPTがプログラム、MHとMTがメモリで、PTの先頭がプログラムポインタ、MTの先頭がメモリポインタです。

標準出力もStdOutという名前でリストで持っていて、実行が終わると

// Finish
template<class PH, class MH, class MT, class StdOut>
struct BF<PH, Null, MH, MT, StdOut> {
  typedef typename Reverse<StdOut>::Result Result;
};

でReverseして返されます。

最後にオーバーローディングされたPrint関数を呼び出す事で結果の型リストを表示しています。-O2をかけるとネストした関数呼び出しがフラットになって、mainではputcharを連続して呼び出すだけのコードになります。

条件分岐のたびに別の特殊化したテンプレートを実体化する必要があり、またg++は末尾呼び出しの最適化を行ってくれないので、あまり実行ステップの多いプログラムを実行する事はできません。HelloWorldを実行するだけでもデフォルトのオプションではだめで、コンパイルは

g++ -ftemplate-depth-1000 brainfuck.cc

のようにしてテンプレート実体化の深さの制限を増やしてやる必要があります。

関数定義があちこちに散らばってしまうのでとても書きづらいですが、引数のパターンマッチングが出来るのはなかなか気持ちがいいですね。

ICPC国内予選C その2

予定してませんでしたが。そして多分その2で終わりです。

昨日学内の練習会でImos Judge(http://judge.imoz.jp/)を利用させて頂いて国内予選の復習をしていたのですが、そこで「Cの制限時間が厳しくて通らない」という話題で少し盛り上がっていました。
厳しいといっても、他の問題の制限時間が10secの中でCだけ15secなので緩いはずなんですが、普通に書くと10! * 12 * 8になってしまって通りません。

しばらくするとチームメイトのH君と他チームコーチのT君が「アルファベットごとの係数を先に求めてしまえば良い」という事に気がつきました。これで10! * 10になって1/10位の時間で動いてくれるはずです（実際には12 * 8のテストケースはそれほど無いようで1/4程度にしかなりませんでしたが）。

例えば最初のテストケースだと

3
ACM
IBM
ICPC

出現するアルファベット

ABCIMP

係数つきの方程式

100*A + 10*B + 10*C + 100*I + 2*M = 1000*I + 101*C + 10*P

左辺から右辺を引く。この等式が成り立つようなアルファベットの値の組を全探索すれば良い事になります。

100*A + 10*B - 91*C - 900*I + 2*M - 10*P = 0

早速実装。ソースはとてもすっきり。

#include <iostream>
#include <set>
#include <vector>

using namespace std;

bool not_zero[10];
int coefficient[10];

int Dfs(int depth, int alphabet_size, int used, int lr) {
  if (depth == alphabet_size) {
    return lr == 0;
  } else {
    int ret = 0;
    for (int i = not_zero[depth] ? 1 : 0; i < 10; ++i) {
      if (used & (1 << i)) continue;
      ret += Dfs(depth + 1, alphabet_size, (used | (1 << i)), lr + coefficient[depth] * i);
    }
    return ret;
  }
}

int main() {
  int N;
  while (cin >> N, N) {
    vector<string> v(N);
    set<char> alph;
    for (int i = 0; i < N; ++i) {
      cin >> v[i];
      for (int j = 0; j < v[i].size(); ++j)
        alph.insert(v[i][j]);
    }

    string alphabet(alph.begin(), alph.end());

    vector<vector<int> > words(N);
    for (int i = 0; i < v.size(); ++i)
      for (int j = 0; j < v[i].size(); ++j)
        words[i].push_back(alphabet.find(v[i][j]));

    fill(coefficient, coefficient + 10, 0);
    for (int i = 0; i < N - 1; ++i)
      for (int j = words[i].size() - 1, ten = 1; j >= 0; --j, ten *= 10)
        coefficient[words[i][j]] += ten;
    for (int i = words.back().size() - 1, ten = 1; i >= 0; --i, ten *= 10)
      coefficient[words.back()[i]] -= ten;

    fill(not_zero, not_zero + 10, false);
    for (int i = 0; i < v.size(); ++i)
      if (v[i].size() > 1)
        not_zero[alphabet.find(v[i][0])] = true;

    cout << Dfs(0, alphabet.size(), 0, 0) << endl;
  }
}

55行になりました。Imos Judgeもこれで通ります。

さて、上のプログラムは制限時間15secのところ11.564secで通ったのですが、Judgeの実行履歴を見ると恐ろしい事に3sec程度で通している人たちがいます（しかも一発目で）。どうなってんだこれ、って事でみんなでしばらく考え、定数倍の最適化を施して何度か送信するも10secを切る事すら叶いませんでした。

その場は解散になったのですが、家に帰る途中に考えてみると…
・求めたいのは、アルファベットが変数となっている式の値が0になる組み合わせの数
・アルファベットを前半と後半に分けて、それぞれ組み合わせを全探索した後に和が0になる組を数えれば良さそう
・一つの組が持つのは(値, 使用した数字(ビットで持つ))で…
・使用した数字が重複せず、さらに値の和が0になるような組み合わせを数える
・ソートして尺取りでやればO(nlogn + n) = O(nlogn)で終わる
・（というかSRMで見かけたような…）

というわけで、実装は綺麗じゃないですが、O(nlogn) ( ただし、n = (N / 2)! )のプログラムになりました。以下ソース。

#include <iostream>
#include <set>
#include <map>
#include <vector>

using namespace std;

bool not_zero[10];
int coefficient[10];

struct S {
  int value, used;
  S(int value, int used) : value(value), used(used) {}
  bool operator<(const S& s) const {
    return value != s.value ? value < s.value : used < s.used;
  }
};

void Dfs(int depth, int alphabet_size, int used, int lr, map<S, int>& m) {
  if (depth == alphabet_size) {
    ++m[S(lr, used)];
  } else {
    for (int i = not_zero[depth] ? 1 : 0; i < 10; ++i) {
      if (used & (1 << i)) continue;
      Dfs(depth + 1, alphabet_size, used | (1 << i), lr + coefficient[depth] * i, m);
    }
  }
}

int main() {
  int N;
  while (cin >> N, N) {
    vector<string> v(N);
    set<char> alph;
    for (int i = 0; i < N; ++i) {
      cin >> v[i];
      for (int j = 0; j < v[i].size(); ++j)
        alph.insert(v[i][j]);
    }

    string alphabet(alph.begin(), alph.end());

    vector<vector<int> > words(N);
    for (int i = 0; i < v.size(); ++i)
      for (int j = 0; j < v[i].size(); ++j)
        words[i].push_back(alphabet.find(v[i][j]));

    fill(coefficient, coefficient + 10, 0);
    for (int i = 0; i < N - 1; ++i)
      for (int j = words[i].size() - 1, ten = 1; j >= 0; --j, ten *= 10)
        coefficient[words[i][j]] += ten;
    for (int i = words.back().size() - 1, ten = 1; i >= 0; --i, ten *= 10)
      coefficient[words.back()[i]] -= ten;

    fill(not_zero, not_zero + 10, false);
    for (int i = 0; i < v.size(); ++i)
      if (v[i].size() > 1)
        not_zero[alphabet.find(v[i][0])] = true;

    map<S, int> head;
    Dfs(0, alphabet.size() / 2, 0, 0, head);
    map<S, int> tail;
    Dfs(alphabet.size() / 2, alphabet.size(), 0, 0, tail);

    vector<pair<S, int> > h(head.begin(), head.end());
    vector<pair<S, int> > t(tail.rbegin(), tail.rend());

    int answer = 0;
    for (int i = 0, j = 0; i < h.size() && j < t.size();) {
      int hv = h[i].first.value, tv = t[j].first.value, value = hv + tv;
      if (value < 0) {
        ++i;
      } else if (value > 0) {
        ++j;
      } else {
        for (int k = i; k < h.size() && h[k].first.value == hv; ++k) {
          for (int l = j; l < t.size() && t[l].first.value == tv; ++l) {
            if ((h[k].first.used & t[l].first.used) == 0) {
              answer += h[k].second * t[l].second;
            }
          }
        }
        while (i < h.size() && h[i].first.value == hv) ++i;
        while (j < t.size() && t[j].first.value == tv) ++j;
      }
    }
    cout << answer << endl;
  }
}

Imos Judgeに送信してみると0.897sec。なかなか良さげです。

ICPC国内予選C

模擬国内予選と国内予選の参加記も書くつもりですが、取り急ぎCのソースだけ！
Cは一見楽勝に見えてそのまま書き始めると実にかったるい（next_permutationを使ってしまったり）ですが、問題文を読み込めばDFSですっきり書けます。

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int value[10];
bool used[10];
bool not_zero[10];

inline int Eval(const vector<int>& word) {
  int ret = 0;
  for (int i = 0; i < word.size(); ++i)
    ret = ret * 10 + value[word[i]];
  return ret;
}

int Dfs(int depth, int alphabet_size, const vector<vector<int> >& words) {
  if (depth == alphabet_size) {
    int left = 0;
    for (int i = 0; i < words.size() - 1; ++i)
      left += Eval(words[i]);
    int right = Eval(words.back());
    return left == right;
  } else {
    int ret = 0;
    for (int i = not_zero[depth] ? 1 : 0; i < 10; ++i) {
      if (used[i]) continue;
      used[i] = true;
      value[depth] = i;
      ret += Dfs(depth + 1, alphabet_size, words);
      used[i] = false;
    }
    return ret;
  }
}

int main() {
  int N;
  while (cin >> N, N) {
    vector<string> v(N);
    set<char> alph;
    for (int i = 0; i < N; ++i) {
      cin >> v[i];
      for (int j = 0; j < v[i].size(); ++j)
        alph.insert(v[i][j]);
    }

    string alphabet(alph.begin(), alph.end());

    vector<vector<int> > words(N);
    for (int i = 0; i < v.size(); ++i)
      for (int j = 0; j < v[i].size(); ++j)
        words[i].push_back(alphabet.find(v[i][j]));

    fill(not_zero, not_zero + 10, false);
    for (int i = 0; i < v.size(); ++i)
      if (v[i].size() > 1)
        not_zero[alphabet.find(v[i][0])] = true;

    fill(used, used + 10, false);
    cout << Dfs(0, alphabet.size(), words) << endl;
  }
}

以上64行。
あ、もちろん本番はnext_permutationを使って無駄にカウントしてしまったのを無理矢理factorialで割りつじつま合わせて提出キめました。

Aho-Corasick

Spaghetti Sourceの複数パターン検索 (Aho-Corasick)で紹介されているスライドを参考にして、書かれている疑似コードをほぼそのままC++で書き直してみたもの。

Trieのvalues_フィールドが保持しているのは、そのノードに到達した時点でマッチしている単語の集合。ここではvectorになっているが、速度が要求されるならばvectorにして添字を保存しても良いし、単語数が少ないならば情報をビットに詰め込んでしまっても良い。実際UVA 11019 - Matrix Matcherを解く際には、単語数が100以下と少なく、また速度が要求されていたため、long long [2]とした（その場合下記の和集合を求める処理が論理和で済んでしまう）。

スライドのp14にあるout(u) := out(u) ∪ out(f (u));に相当する処理は

          for (int i = 0; i < u->fail_->values_.size(); ++i) {
            u->values_.push_back(u->fail_->values_[i]);
          }

となっている。これは少々重たい気がする。実際この処理を飛ばしてMatchメソッドを

  void Match(const string& text) {
    Trie* current = root_;
    for (int i = 0; i < text.size(); ++i) {
      int c = text[i];
      while (!current->edge_[c]) {
        current = current->fail_;
      }
      current = current->edge_[c];
      // 次の行が増えた
      for (Trie* t = current; current != current->fail_; current = current->fail_) {
        for (int i = 0; i < t->values_.size(); ++i) {
          cout << t->values_[i] << endl;
        }
      }
    }
  }

のように書き換えても動作は変わらない。これは何度か試してみたのだけれど、遅くなるだけだったのでやめた。オートマトン構築のコストより検索のコストがボトルネックになる事が多いので、そこは気にしないで良いのかも。

#include <iostream>
#include <vector>
#include <queue>
#define MAX 256

using namespace std;

class Aho {
 public:
  Aho(const vector<string>& v) {
    root_ = new Trie();
    for (int i = 0; i < v.size(); ++i) {
      root_->insert(v[i]);
    }

    for (int i = 0; i < MAX; ++i) {
      if (!root_->edge_[i]) {
        root_->edge_[i] = root_;
      }
    }
    root_->fail_ = root_;

    queue<Trie*> que;
    for (int i = 0; i < MAX; ++i) {
      Trie* q = root_->edge_[i];
      if (q != root_) {
        q->fail_ = root_;
        que.push(q);
      }
    }
    while (!que.empty()) {
      Trie* r = que.front(); que.pop();
      for (int i = 0; i < MAX; ++i) {
        Trie* u = r->edge_[i];
        if (u) {
          que.push(u);
          Trie* v = r->fail_;
          while (!v->edge_[i]) {
            v = v->fail_;
          }
          u->fail_ = v->edge_[i];
          for (int i = 0; i < u->fail_->values_.size(); ++i) {
            u->values_.push_back(u->fail_->values_[i]);
          }
        }
      }
    }
  }

  ~Aho() { delete root_; }

  void Match(const string& text) {
    Trie* current = root_;
    for (int i = 0; i < text.size(); ++i) {
      int c = text[i];
      while (!current->edge_[c]) {
        current = current->fail_;
      }
      current = current->edge_[c];
      for (int i = 0; i < current->values_.size(); ++i) {
        cout << current->values_[i] << endl;
      }
    }
  }

 private:

  class Trie {
   public:
    Trie() {
      for (int i = 0; i < MAX; ++i) {
        edge_[i] = NULL;
      }
      fail_ = NULL;
    }

    ~Trie() {
      for (int i = 0; i < MAX; ++i) {
        if (edge_[i] && edge_[i] != this) {
          delete edge_[i];
        }
      }
    }

    void insert(const string& s) {
      Trie* t = this;
      for (int i = 0; i < s.size(); ++i) {
        int c = s[i];
        if (!t->edge_[c]) t->edge_[c] = new Trie();
        t = t->edge_[c];
      }
      t->values_.push_back(s);
    }

   private:
    friend class Aho;
    Trie* edge_[MAX];
    Trie* fail_;
    vector<string> values_;
  };

  Trie* root_;
};

int main() {
  vector<string> dictionary;
  dictionary.push_back("he");
  dictionary.push_back("she");
  dictionary.push_back("his");
  dictionary.push_back("hers");

  Aho aho(dictionary);
  string text = "ushers";
  aho.Match(text);
}

KMPとかACとか、文字列検索系の問題

KMP Algorithm - Search for Problemsに載っているのをちょこちょこ送信中。UVaは掲示板書き込みの英語率が高いのが良い。

UVa 10975 Dueue's Quiz

長さ1000以下の単語が最大15000個与えられる。最大100*100の文字テーブルの中に出現する単語を全て数え上げよ。文字テーブルの読み方は、縦横斜めをそれぞれ双方向。

Aho-Corasick、だけれど、細かい所で注意しないといけない微妙な問題。具体的には以下。

• cin, coutを使用すると時間がきつい。
• 長さ100以下の単語以外はテーブルに収まらないので無視。
• 重複する単語があるので削除