strings.tex

\section{Strings}

\subsection{KMP}
\begin{verbatim}
std::vector<int> compute_prefix(std::string p) {
   int m = p.size();

   std::vector<int> pi(m);
   int k = 0;

   pi[0] = 0;
   for (int q = 1; q < m; q++) {
      while(k > 0 && p[k] != p[q])
         k = pi[k - 1];
      if (p[k] == p[q])
         k++;
      pi[q] = k;
   }
   return pi;
}

void kmp_match(std::string s, std::string p) {
   std::vector<int> pi = compute_prefix(p);
   int q = 0;
   int n = s.size();
   int m = p.size();

   for(int i = 0; i < n; i++) {
      while (q > 0 && p[q] != s[i])
         q = pi[q - 1];
      if (p[q] == s[i])
         q++;
      if (q == m) {
         std::cout << "Match pos "
            << (i - m + 1)
            << std::endl;
      }
   }
}
\end{verbatim}

\subsection{Range Minimum Query}
\begin{verbatim}
int main() {
   int N,Q,i,j,k;

   scanf("%d %d",&N,&Q);

   for (i=0;i<N;i++)
            scanf("%d",&n[i]);

   for (i=0;i<N;i++)
            m[i][0]=M[i][0]=n[i];

   for (i=1;(1<<i)<=N;i++) {
            for (j=0;j+(1<<i)-1<N;j++) {
               m[j][i]=min(m[j][i-1],m[j+(1<<(i-1))][i-1]);
               M[j][i]=max(M[j][i-1],M[j+(1<<(i-1))][i-1]);
            }
   }

   for (k=0;k<Q;k++) {
            scanf("%d %d",&i,&j);
            i--;j--;
            int t,p;
            t=(int)(log(j-i+1)/log(2));
            p=1<<t;
            printf("%d\n",max(M[i][t],M[j-p+1][t])
            - min(m[i][t], m[j - p + 1][t]));
   }
   return 0;
}
\end{verbatim}
$$
M[i][j]=\max(M[i][j-1],M[i+2^{j-1}][j-1])
$$
$$
RMQ_A(i,j)=\max(M[i][k],M[j-2^k+1][k])
$$

\subsection{Nth Permutation}
\begin{verbatim}
/**
  * Computes kth (0 to s.size()! - 1) permutation
  * of string s
  */
std::string nth_permutation(uint64_t k, const std::string &s) {
    uint64_t factorial = 1;
    for (uint64_t i = 1; i <= s.size(); ++i) {
        factorial *= i;
    }

    std::string s_copy = s;
    std::string res;
    for (uint64_t j = 0; j < s.size(); ++j) {
        // compute how many permutations on the rest
        // of the string s[j + 1 .. s.size() - 1]
        factorial /= s.size() - j;

        // store character 
        uint64_t l = k / factorial;
        res += s_copy[l];

        // remove already used character
        s_copy.erase(s_copy.begin() + l);

        // compute new value of k
        k = k % factorial;
    }
    return res;
 }
\end{verbatim}