AOJ 1170: Old Memories

Problem

国内予選の時間制限を考えると、1チームもこれを解かなかったというのがちょっと意外です。

Problem

Algorithm

  • 参加記録に書いたものと同じ。以下コピペ。

  • 編集距離 d 以下の文字列を全列挙する。
    • これは愚直にやる。
      • 挿入・削除・置換がそれぞれ (40*27), (40), (40*27) 通りぐらいあるので、1回でざっと 2,400 分岐。
        • d <= 2 なのでおよそ 2,4002個。全列挙できなくも無い。
  • 全列挙したそれぞれの文字列について、作成可能かどうか線形時間で判定する。
    • それにはローリングハッシュを使う。というか Rabin-Karp.
      • あらかじめ、全てのピースのハッシュ値を求めておく。
      • ローリングハッシュを使うと、その文字列のある長さの全ての substring のハッシュ値を線形時間で求められる。
        • つまり、いずれかのピースとマッチした位置を線形時間で全て求められる。
    • マッチした位置と各ピースの長さが分かってるのだから、ピースで覆えるかの判定も簡単に出来る。

  • 書かなかった/後で試した試行錯誤はこんな感じ。
    • stringを使わずにchar配列で頑張る
      • 全然速くならなかった上に、ちょっとバグったのでボツ。
        • stringは遅いという認識を改めたほうがよさそう。
    • 既に生成した文字列を蓄えておき、再計算を避ける
      • これが諸悪の根源だった。メモリをバカ食いするせいか、d = 2 のケースではむしろ5倍ぐらい遅くなります。
        • 考えてみれば、ピースで覆えるかどうかの判定は線形なのだから、必死で枝を刈る必要もないよね。
    • 必ず replace -> insert -> delete の順番で操作する
      • この順番に限ったとしても、編集距離は特に変わらない。はず。厳密に証明してないけど。
      • ちょっと速くなったけど、期待したほどではなかった。
  • エレガントなアルゴリズムでさっくり解いてくれる偉い人募集中です。

Code

  • ジャッジデータ F1 に通りました。実行時間は3分弱。
    • 国内予選ルールならきっと正解だよね。
  • スパゲッティですがご容赦ください。
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define FOR(i,b,n) for(int i=(b);i<(int)(n);++i)
#define EACH(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it)

using namespace std;

typedef vector<int> vint;
// typedef unsigned long long Hash;
typedef unsigned int Hash;          // 追記: 32bitで十分だった

const char LET[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ.";

const int N=30;
const Hash H=10007;

int l;
set<string> ans;
set<Hash> hs;

inline bool ok(const string &s){
  static bool v[64];
  REP(i,64) v[i]=false;

  Hash hash=0, c=1;
  REP(i,l){ hash*=H; hash+=s[i]; c*=H; }
  if(hs.count(hash)) v[0]=true;

  REP(i,s.length()-l+1){
    hash*=H; hash-=s[i]*c; hash+=s[i+l];
    if(hs.count(hash)) v[i+1]=true;
  }

  if(!v[0]) return false;
  int oklen=0;
  REP(i,s.length()){
    if(i>oklen) return false;
    if(v[i]) oklen=i+l;
  }

  return oklen>=s.length();
}

enum{ REPLACE, INSERT, DELETE };

void rec(string s,int r,int last = REPLACE){
  if(!r){ 
    if(ok(s)) ans.insert(s);
    return; 
  }
  
  // replace
  if(last == REPLACE){
    REP(i,s.length()) REP(j,27){
      char c=s[i]; s[i]=LET[j]; 
      rec(s,r-1,REPLACE);
      s[i]=c;
    }
  }

  
  // insert
  if(last == REPLACE || last == INSERT){
    REP(i,s.length()+1) REP(j,27){
      string t=s;
      t.insert(t.begin()+i,LET[j]);
      rec(t,r-1,INSERT);
    }
  }

  // delete
  REP(i,s.length()){
    string t=s;
    t.erase(t.begin()+i);
    rec(t,r-1,DELETE);
  }
}

void solve(string s,int n,int d){
  ans.clear();
  rec(s,d);

  cout << ans.size() << endl;
  if((int)ans.size()<=5){
    EACH(it,ans) cout << *it << endl;
  }
}

int main(){
  int d,n;
  while(cin >> d >> n && d|n){
    string w[N];
    string text;
    cin >> text;
    REP(i,n) cin >> w[i];

    l=w[0].length();

    Hash hash[N];
 
    REP(i,n){
      hash[i]=0;
      REP(j,l){ hash[i]*=H; hash[i]+=w[i][j]; }
    }
    
    hs.clear();
    hs.insert(hash,hash+n);

    solve(text,n,d);
  }
}