Suffix Array

// Suffix Array は接尾辞配列です。
// 例えば"abcab"の接尾辞は"abcab"や"bcab"や"cab"などです。
// すべての接尾辞を辞書順に並べて元のインデックスを記録したものをSuffix Arrayといいます。
// "abcab"の場合、{5,3,0,4,1,2}となります(最後に空文字""があるとする)。
// 辞書順なので2分探索を使った高速な検索が可能です。
// LCPはSuffix Arrayの次の接尾辞と先頭が何文字一致するかを記録したものです。
// SuffixArray内での文字列比較を効率良く行うことができます。
// "abcab"の場合、{0,2,0,1,0,0}となります。
//
// sa lcp "string"
// 5 0 ""
// 3 2 "ab"
// 0 0 "abcab"
// 4 1 "b"
// 1 0 "bcab"
// 2 0 "cab"
//
// 最後に空文字""が入るので文字列の長さに+1するのを忘れずに。
// init_sa はSuffix Arrayを作成 O(nlog2n)
// contain は文字列SにTが含まれるかを調べる O(TlogS)
// int_lcp はLCPを作成 O(n)

#define MAX_N 100005

long long sn, sk;
long long rank[MAX_N+1];
long long tmp[MAX_N+1];

bool compare_sa(long long i, long long j){
  if(rank[i] != rank[j])return rank[i] < rank[j];
  else{
    long long ri = i + sk <= sn ? rank[i + sk] : -1;
    long long rj = j + sk <= sn ? rank[j + sk] : -1;
    return ri < rj;
  }
}

void init_sa(string S, long long *sa){
  sn = S.size();
  for(long long i = 0; i <= sn; i++){
    sa[i] = i;
    rank[i] = i < sn ? S[i] : -1;
  }
  for(sk = 1; sk <= sn; sk *= 2){
    sort(sa,sa+sn+1,compare_sa);
    tmp[sa[0]] = 0;
    for(long long i = 1; i <= sn; i++){
      tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1],sa[i]) ? 1 : 0);
    }
    for(long long i = 0; i <= sn; i++){
      rank[i] = tmp[i];
    }
  }
}

long long contain(string S, long long *sa, string T){
  long long a = 0;
  long long b = S.size();
  while(b-a>1){
    long long c = (a+b)/2;
    if(S.compare(sa[c],T.length(),T)<0)a=c;
    else b=c;
  }
  return S.compare(sa[b],T.size(),T)==0 ? 1 : 0;
}

void init_lcp(string S, long long *sa, long long *lcp){
  sn = S.size();
  for(long long i = 0; i <= sn; i++){
    rank[sa[i]] = i;
  }
  long long h = 0;
  lcp[0] = 0;
  for(long long i = 0; i < sn; i++){
    long long j = sa[rank[i]-1];
    if(h>0)h--;
    for(;j+h<sn&&i+h<sn;h++){
      if(S[j+h]!=S[i+h])break;
    }
    lcp[rank[i]-1] = h;
  }
}

long long sa[100010];
long long lcp[100010];
string s = "abcab";
init_sa(s,sa);
init_lcp(s,sa,lcp);