The first doubling SA that worked... This post will be updated soon. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e4 + 4; char s[ MAXN ]; struct suffix_array{ // O( N lg N lg N ) int n; vector< int > sa; suffix_array( const char *s ) :</bits/stdc++.h>…

Counts the frequency of each pattern in text. O( SIGMA( | P | ) ) string T; vs pattern; map< char, int > mci; struct node{ int val; int nxt[ 6 ]; }; vector< node > tree; int cnt = 1, num = 0, n; vi f, lst, occ_cnt; queue< int > que; map< s…

Burrows-Wheeler Transform and its inverse. See this and this. // BWT, O( N ^ 2 lg N ) due to SA string s; int slen; vi sa; bool sa_cmp( const int i, const int j ){ return s.substr( i, slen ) < s.substr( j, slen ); } void solve(){ cin >> s;…

Here are only a few rough notes I have grasped recently, and would probably not make much sense to any of you.First, it is proved that all NP problems ( Hamiltonian Path, Graph Coloring etc. ) can be reduced to SAT problem. One example is …