I worked in DNA K-mers counting and I prepare this formulation to solve the counting using perfect hash table :
![enter image description here][1]
![enter image description here][2]




Using Rcpp API(C++) to integrate the code into R:

   


     #include <Rcpp.h>
        using namespace Rcpp;
        /*
        this code can be used with c++ by replacing IntegerVector by std::vector<int>
        */
        //************************************************
        inline const short int V (const char x){
          switch(x){
          case 'A':case 'a':
            return 0;
            break;
          case 'C':case 'c':
            return 1;
            break;   
          case 'G':case 'g':
            return 2;
            break;
          default:
            return 3;
          break;  
          }
        
        }
        
        inline unsigned int  X0( const std::string A,const int k ,const int n){
          unsigned int  result=0;
          int j=k;
          for( int i=n-1;i>n-k-1;i--) {
            result+= pow(4,k-j)*V(A[i]);
          j--;
          }
          return result;
        }
        
        // [[Rcpp::export]]
        inline IntegerVector kmer4(const std::string A,const int n,const int k)
        {
        
          IntegerVector P(pow(4,k));                  
          int x=X0(A,k,n);                              
          P[x]++;                   
          const int N=pow(4,k-1);               
          for( int i=n-k-1;i>-1;i--){
            x=N*V(A[i])+x/4-x%4/4;
            P[x]++;
          }
          return P;
        }

There are two questions:

Assuming the index x of a kmer,the compliment of x is then (4^k)-x-1. Can we get the reverse using a numeric operation like preceding formula?
There are two problems in running time: iteration over the string and vector creation where the k is over then 8. Are there ideas to solve these problems?


  [1]: https://s15.postimg.org/dwqyrpbvv/Capture.jpg
  [2]: https://s15.postimg.org/o7iozlzfv/Capture2.jpg
 I think that the problem is solved using this code using incrementation.  

    inline unsigned int  X1( const std::string A,const int k ){
      unsigned int  result=V(A[0]);
      for( int i=1;i<k;i++) {
        result+= pow(4,i)*V(A[i]);
      }
      return result;
    }
    
      
      // [[Rcpp::export]]
      inline IntegerVector rc_kmer4(const std::string A,const int n,const int k)
      {
        const int np=k-1;
        const int Lim=n-np;             //---- number of subsequence 
        const int beta=pow(4,k);
        const int N=pow(4,np);               
        unsigned short int fo,ba;// forword and backword of substring
        IntegerVector P(beta);    
        unsigned int x=X1(A,k);
        unsigned int y=X0(A,k,k);
        P[beta-x-1]++;
        P[y]++;
        for( int i=1;i<Lim;i++){
          fo=V(A[i-1]);
          ba=V(A[i+np]);
          x=(x-fo)/4+ba*N;
          y=4*y-beta*fo+ba;
          P[beta-x-1]++;
          P[y]++;
        }
        return P;
      }
  

It works with linear complexity. 
Think you for ideas @John