AOJ 2614 : Almost Same Substring

問題概要 :　略

解法 :
SuffixArray + LCP + RMQ で頑張った

与えられた２つの文字列を結合する
その際に間には大きな文字を入れる
S = S + "$" + T' + "$"
この S の SuffixArray, LCP を作成する
LCP 内の区間[a,b)の最小値を求めるRMQを用意する

左から１つずつ見ていく
今見ている場所 i から i+|T'|-1 までの文字列が T' と何文字異なるかを判定する
異なる文字数を diff とする、初期値は０
LCP内の区間[min(iのある場所,S内でT'が始まる場所),max(iのある場所,S内でT'が始まる場所) ) の最小値だけ先頭が一致しているため、その文だけ先にすすめる
最小値が０の時、先頭の1文字が一致していないので diff を１増やし先頭を１つ先に移動する
diff >= 2 になった時、条件を満たさないため終わる
全て終わった後に diff が１かどうかで判定

今回は1文字異なるかどうかだが、この方法なら任意の文字数だけ異なるかどうかを ( 異なる文字数 ) * 2 回の処理で求めることができる

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int IINF = INT_MAX;

class RMQ{
private:
  int limit,N;
  vector<int> dat;
public:
  void init(int n_){
    N = n_;
    limit = 1;
    while(limit<n_)limit*=2;
    dat.clear();
    dat.resize(2*limit,IINF);
  }
  
  int _build(int cur,int L,int R,const vector<int> &buf){
    if( !( 0 <= cur && cur < 2*limit ) ) return IINF;
    if( L == R-1 ) {
      if( L >= N ) return IINF;
      dat[cur] = buf[L];
    } else {
      int vl = _build(cur*2+1,L,(L+R)/2,buf);
      int vr = _build(cur*2+2,(L+R)/2,R,buf);
      dat[cur] = min(vl,vr);
    }
    return dat[cur];
  }

  void build(const vector<int> &buf){ _build(0,0,limit,buf); };
 
  int _query(int a,int b,int k,int l,int r){
    if(r<=a || b<=l)return IINF;
    else if(a<=l && r<=b)return dat[k];
    int vl = _query(a,b,k*2+1,l,(l+r)/2);
    int vr = _query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }

  int query(int a,int b){ return _query(a,b,0,0,limit); }
};

string s,t;
vector<int> SuffixArray,LCP,vec;
RMQ rmq;

struct CompareSA{
  int k;
  const vector<int> &rank;
  CompareSA(const int k,const vector<int> &rank) : k(k), rank(rank){}
  bool operator()(int i,int j) {
    if( rank[i] != rank[j] ) return rank[i] < rank[j];
    int ri = i + k < (int)rank.size() ? rank[i+k] : -1;
    int rj = j + k < (int)rank.size() ? rank[j+k] : -1;
    return ri < rj;
  }
};
  
vector<int> build_sa(const string &s){
  int n = s.size();
  vector<int> sa(n+1), rank(n+1), tmp(n+1);
  rep(i,sa.size()){
    sa[i] = i;
    rank[i] = i < n ? s[i] : -1;
  }
  for(int k=1;k<=n;k*=2){
    CompareSA comp(k,rank);
    sort(sa.begin(),sa.end(),comp);
    tmp[sa[0]] = 0;
    for(int i=1;i<=n;i++) tmp[sa[i]] = tmp[sa[i-1]] + comp(sa[i-1],sa[i]);
    rank = tmp;
  }
  return sa;
}
  
vector<int> build_lcp(const string &s,vector<int> sa){
  int n = s.size(), h = 0;
  vector<int> rank(n+1), lcp(n+1);
  rep(i,n+1) rank[sa[i]] = i;
  rep(i,n) {
    int j = sa[rank[i]-1];
    if( h > 0 ) h--;
    for(; j + h < n && i + h < n; h++ ) if( s[j+h] != s[i+h] ) break;
    lcp[rank[i]-1] = h;
  }
  return lcp;
}

inline bool isValid(int a,int b,int c,int d){
  if( ( b - a ) != ( d - c ) ) return false;
  if( a == c && b == d ) return true;
  int p1 = a, p2 = c, diff = 0;
  while( diff <= 1 && a <= b ){
    int L1 = vec[a];
    int L2 = vec[c];
    int coef = rmq.query(min(L1,L2),max(L1,L2));
    if( coef == 0 ) {
      ++diff, ++a, ++c;
      continue;
    }
    a += coef, c += coef;

  }
  return diff == 1;
}


int main(){
  cin >> s >> t;
  int n = s.size(), m = t.size();
  s = s + "$" + t + "$";
  SuffixArray = build_sa(s);
  LCP         = build_lcp(s,SuffixArray);
  vec.resize(SuffixArray.size()+1,-1);
  rmq.init(LCP.size());
  rmq.build(LCP);

  rep(i,SuffixArray.size()) vec[SuffixArray[i]] = i;

  int answer = 0;
  rep(i,n-m+1) if( isValid(i,i+m-1,n+1,n+1+m-1) ) ++answer;
  cout << answer << endl;
  return 0;
}