kktkbwt benchmark

// https://qiita.com/kktk-KO/items/82a567e562ccf0ed5d09

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>
#include <cstring>

namespace kktkbwt {

template <class Iterator>
struct default_lexically_lesser
{
  bool operator() (Iterator left, Iterator right) noexcept
  {
#if 0
    if (*left == '\0' && *right == '\0') { return false; }
    if (*left == '\0' && *right != '\0') { return true; }
    if (*left != '\0' && *right == '\0') { return false; }
    return *left < *right || (*left == *right && (*this)(++left, ++right));
#else
    for(;*left == *right && *left != '\0';++left,++right);
    return *left < *right;
#endif
  }
};

template <
  class RandomAccessIterator1,
  class RandomAccessIterator2,
  class OutputIterator,
  class DifferenceType,
  class LexicallyLesser = default_lexically_lesser<RandomAccessIterator1>
>
void bwt (RandomAccessIterator1 in, RandomAccessIterator2 aux, OutputIterator out, DifferenceType size)
{
  for (DifferenceType i = 0; i < size; ++i) { aux[i] = i; }

  std::sort(aux, aux + size, [&] (DifferenceType l, DifferenceType r) {
    return LexicallyLesser()(in + l, in + r); }
    //return strcmp(in+l,in+r)<0; }
  );

  for (DifferenceType i = 0; i < size; ++i) { out[i] = in[(aux[i] + size - 1) % size]; }
}

}

namespace ciel {
struct sorter{
    //string str;
    const char *p;
    sorter(std::string &_str):p(_str.c_str()){}
    //bool operator()(const int a, const int b) const{return str.substr(a)<str.substr(b);}
    bool operator()(const int a, const int b) const{return strcmp(p+a,p+b)<0;}
};
std::vector<int> buildSA(std::string &t){
    int n=t.size();
    std::vector<int>suff(n);
    for(int i=0;i<n;i++)suff[i]=i;
    std::sort(suff.begin(),suff.end(),sorter(t));
    return suff;
}
}

namespace prefield {
struct SAComp{
    const int h,*g;
    SAComp(const int h, const int* g) : h(h), g(g) {}
    bool operator()(const int a, const int b){
        return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h];
    }
};
std::vector<int> buildSA(std::string &t){
    int n=t.size();
    int g[n],b[n];
    std::vector<int>suff(n);
    for(int i=0;i<n;i++)suff[i]=i,g[i]=t[i];
    b[0]=b[n-1]=0;
    std::sort(suff.begin(),suff.end(),SAComp(0,g));
    for(int h=1;b[n-1]!=n-1;h<<=1){
        SAComp comp(h,g);
        std::sort(suff.begin(),suff.end(),comp);
        for(int i=0;i<n-1;i++)b[i+1]=b[i]+comp(suff[i],suff[i+1]);
        for(int i=0;i<n;i++)g[suff[i]]=b[i];
    }
    return suff;
}
}

std::string buildBWT(std::string &t,std::vector<int> &suff){
    int n=t.size();
    std::string bw;
    for(int i=0;i<n;i++)bw+=t[(suff[i]?:n)-1];
    return bw;
}

int main(){
    //manual
    //std::string str="banana$";
    //std::string str="TACGTAATCATGCGGCTAGCGCATGCATGCGTAGCGCATCGTAGCTC$";

    //repeat
    std::string str(50000,'a'); str+='$';

    /*
    //random
    std::string str;
    {
        std::mt19937 engine(123456789);
        std::uniform_int_distribution<> dist(0,26);
        for(int i=0;i<100000;i++){
            str+='a'+dist(engine);
        }
        str+='$';
    }
    */

    std::cin.tie(0);
    std::ios::sync_with_stdio(false);

    for(int i=0;i<2;i++){
    {
        auto start = std::chrono::system_clock::now();
        std::vector<int> suff=prefield::buildSA(str);
        std::string bwt=buildBWT(str,suff);
        auto end = std::chrono::system_clock::now();
        //std::cout<<bwt<<std::endl;
        std::cout<<std::chrono::duration_cast<std::chrono::microseconds>(end-start).count()<<std::endl;
    }

    {
        auto start = std::chrono::system_clock::now();
        std::vector<int> suff=ciel::buildSA(str);
        std::string bwt=buildBWT(str,suff);
        auto end = std::chrono::system_clock::now();
        //std::cout<<bwt<<std::endl;
        std::cout<<std::chrono::duration_cast<std::chrono::microseconds>(end-start).count()<<std::endl;
    }

    {
        auto start = std::chrono::system_clock::now();
        std::vector<int> suff(str.size());
        std::string bwt;
        bwt.resize(str.size());
        kktkbwt::bwt(&str[0],&suff[0],&bwt[0],str.size());
        auto end = std::chrono::system_clock::now();
        //std::cout<<bwt<<std::endl;
        std::cout<<std::chrono::duration_cast<std::chrono::microseconds>(end-start).count()<<std::endl;
    }
    }
}