読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj ALDS1_14_C

algorithm algorithm-暗号 algorithm-ハッシュ contest contest-aoj language language-c++11

Pattern Search | Aizu Online Judge

二次元配列の効率的なハッシュの精製方法について

配列  {\displaystyle a_{i,j}} から以下のような行方向のハッシュの配列  {\displaystyle b_{i,j}} を生成する.
 { \displaystyle
b_{i,j} = \sum_{k=0}^{c-1} B_1^{c-1-k} a_{i,j+k}
}
この時
 { \displaystyle
b_{i,j+1} = (b_{i,j} - {B_1}^{c-1}a_{i,j})B_1+a_{i,j+c}
}
のように計算すればO(h)のオーダーでハッシュが計算できる.

同様に以下のような列方向のハッシュの配列  {\displaystyle c_{i,j}}を生成する.
 { \displaystyle
c_{i,j} = \sum_{k=0}^{r-1} B_2^{r-1-k} b_{i+k,j}
}
この時
 { \displaystyle
c_{i,j+1} = (c_{i,j} - {B_2}^{r-1}b_{i,j})B_2+b_{i+r,j}
}
のように計算すればO(w)のオーダーでハッシュが計算できる.
このようにしてハッシュがO(h*w*r*c)からO(h*w*(r+c))のオーダーで計算できるようになる.
なお定数 {\displaystyle B_1,B_2}は適当な互いに素な数(素数が望ましい)を採用すればハッシュの衝突は起こりにくい.

#include <bits/stdc++.h>
#define MOD 1000000007LL
#define C1  401
#define C2  397
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

typedef long long ll;

using namespace std;

int h,w,r,c;

vector<vector<ll> > genHash(const vector<string> v, int xs, int ys)
{
  vector<vector<ll> > h1(xs,vector<ll>(ys,0));
  vector<vector<ll> > h2(xs,vector<ll>(ys,0));
  ll cn1 = 1, cn2 = 1;
  REP(i,c) cn1 = (cn1*C1)%MOD;
  REP(i,r) cn2 = (cn2*C2)%MOD;
  REP(i,xs)
  {
    ll h = 0;
    REP(j,c) h=(h*C1+v[i][j])%MOD;
    REP(j,ys-c+1)
    {
      h1[i][j] = h;
      if(j+c<ys) h = (h*C1-v[i][j]*cn1+v[i][j+c])%MOD;
      h = (h<0)?h+MOD:h;
    }
  }
  REP(j,ys)
  {
    ll h = 0;
    REP(i,r) h=(h*C2+h1[i][j])%MOD;
    REP(i,xs-r+1)
    {
      h2[i][j] = h;
      if(i+r<xs) h = (h*C2-h1[i][j]*cn2+h1[i+r][j])%MOD;
      h = (h<0)?h+MOD:h;
    }
  }
  return h2;
}

int main()
{
  cin >> h >> w;
  vector<string> a(h);
  REP(i,h) cin >> a[i];
  cin >> r >> c;
  vector<string> b(r);
  REP(i,r) cin >> b[i];
  if(h<r||w<c) return 0;
  auto f = genHash(a,h,w);
  auto p = genHash(b,r,c);
  REP(i,h-r+1) REP(j,w-c+1) if(f[i][j] == p[0][0])
    printf("%d %d\n",i,j);
  return 0;
}