Calculate the average longest common substring exactly
C++, n = 21 (40s on an AMD Ryzen 5 2500U)
This used to be a fast brute force answer that got up to n=17. That is currently preserved in the revision history.
#include &lt;cstring&gt;
#include &lt;omp.h&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;array&gt;
#include &lt;algorithm&gt;
#include &lt;map&gt;
#include &lt;unordered_map&gt;
#include &lt;bitset&gt;
#include &lt;random&gt;

typedef unsigned uint;
typedef unsigned char byte;
const int threadnum = 8;
const int maxn = 22; //for 24 bytes total size of Row
struct Row; struct hasher { size_t operator ()(const Row&amp; row) const; };
struct Row
{
    char max = 0;
    std::array&lt;char, maxn+1&gt; row {0};
    Row() { }
    Row(int nmax)
    {
        max = nmax;
    }
    bool operator ==(const Row&amp; rhs) const
    {
        const uint64_t* x = reinterpret_cast&lt;const uint64_t*&gt;(this);
        const uint64_t* y = reinterpret_cast&lt;const uint64_t*&gt;(&amp;rhs);
        return x[0] == y[0] &amp;&amp; x[1] == y[1] &amp;&amp; x[2] == y[2];
    }
};
uint64_t rotl(uint64_t x, char a)
{
    return (x &lt;&lt; a) | (x &gt;&gt; (64 - a));
}
size_t hasher::operator() (const Row&amp; row) const
{
    const uint64_t* mem = reinterpret_cast&lt;const uint64_t*&gt;(&amp;row);
    //I tried really many different hashes...
    uint64_t h = mem[0]; h += rotl(h, 4);
    h         ^= mem[1]; h += rotl(h, 4);
    h         ^= mem[2]; h += rotl(h, 4);
    return h;
}
const short hashTableSize = 1009;
struct Map
{
    std::array&lt;std::pair&lt;Row, int&gt;, hashTableSize&gt; table {};
    Map()
    {
    }
    void add_or_add(const Row row, const int delta)
    {
        size_t hash = hasher()(row) % hashTableSize;
        while(table[hash].second != 0 &amp;&amp; !(table[hash].first == row))
        {
            hash++;
            if(hash == hashTableSize) hash = 0; //just loop :)
        }
        if(table[hash].second == 0)
            table[hash].first = row;
        table[hash].second += delta;
    }
    void clear()
    {
        std::memset(table.data(), 0, sizeof(table));
    }
};

constexpr uint bitRev(uint n)
{
    n = ((n &gt;&gt; 1) &amp; 0x55555555) | ((n &lt;&lt; 1) &amp; 0xaaaaaaaa);
        n = ((n &gt;&gt; 2) &amp; 0x33333333) | ((n &lt;&lt; 2) &amp; 0xcccccccc);
        n = ((n &gt;&gt; 4) &amp; 0x0f0f0f0f) | ((n &lt;&lt; 4) &amp; 0xf0f0f0f0);
        n = ((n &gt;&gt; 8) &amp; 0x00ff00ff) | ((n &lt;&lt; 8) &amp; 0xff00ff00);
        n = ((n &gt;&gt;16) &amp; 0x0000ffff) | ((n &lt;&lt;16) &amp; 0xffff0000);
        return n;
}
constexpr bool is_substring(int target, char n, short subs, char m)
{
    //n=2, m=1 -&gt; i from 0 to 1
    int max = n-m+1;
    bool flag = false;
    for(int i = 0; i &lt; max; i++)
        flag |= (((target &gt;&gt; i) ^ subs) &amp; ((1&lt;&lt;m) - 1)) == 0;
    return flag;
}
int supermax = 0;
int main()
{
    uint n; std::cin &gt;&gt; n;
    std::vector&lt;uint64_t&gt; sums(threadnum);
    uint64_t sum = 0;
#pragma omp parallel for num_threads(threadnum) schedule(dynamic)
    for(uint sa = 0; sa &lt; 1&lt;&lt;~-n; sa++) //the second half is the bitwise complement of the first one
    {
        uint sb = bitRev(sa);
        sb ^= -(sb &gt;&gt; 31);
        sb &gt;&gt;= 32 - n;
        if(sb &lt; sa) continue;
        //find a lower bound = len(the shortest non-substring of sa) - 1
        //if Row.max is immediately set to it, that reduces the number of states slightly
        char lb = 0; bool found = false;
        for(char len = 0; len &lt; 10; len++)
        {
            for(short j = 0; j &lt; (1&lt;&lt;len); j++)
                if(!is_substring(sa, n, j, len))
                {
                    lb = len - 1;
                    goto out;
                }
        }
        out:;
        Map dpcur;
        Map dpnext;
        dpcur.add_or_add(Row(lb), 1);
        int ans = 0;
        for(char j = 0; j &lt; n; j++)
        {
            for(auto[row, cnt] : dpcur.table)
            {
                if(!cnt) continue;
                Row nr0 {}, nr1 {};
                nr0.max = nr1.max = row.max;
                for(char i = 0; i &lt; n; i++)
                {
                    Row&amp; r = (sa &gt;&gt; i)&amp;1 ? nr0 : nr1;
                    r.row[i+1] = row.row[i] + 1;
                }
                char n0max = 0, n1max = 0;
                for(char i = 0; i &lt; 23; i++)
                    n0max = std::max(n0max, nr0.row[i]);
                for(char i = 0; i &lt; 23; i++)
                    n1max = std::max(n1max, nr1.row[i]);
                //possibly, cut an entire would-be branch that would never improve!
                if(n0max + n - j - 1 &lt;= nr0.max)
                    ans += (cnt * nr0.max) &lt;&lt; (n - j - 1);
                else
                    nr0.max = std::max(nr0.max, n0max), dpnext.add_or_add(nr0, cnt);
                if(n1max + n - j - 1 &lt;= nr1.max)
                    ans += (cnt * nr1.max) &lt;&lt; (n - j - 1);
                else
                    nr1.max = std::max(nr1.max, n1max), dpnext.add_or_add(nr1, cnt);
            }
            std::memcpy(dpcur.table.data(), dpnext.table.data(), sizeof(Map));
            dpnext.clear();
        }
        for(auto[row, cnt] : dpcur.table)
            ans += cnt * row.max;
        sums[omp_get_thread_num()] += ans;
        if(sb != sa)
            sums[omp_get_thread_num()] += ans;
    }
    for(uint64_t e : sums) sum += e;
    sum *= 2;
    printf(&quot;%ld\n&quot;, sum);
    uint64_t num = sum, denom = 1ll&lt;&lt;(2*n);
    while(num % 2 == 0) num /= 2, denom /= 2;
    printf(&quot;%ld/%ld\n&quot;, num, denom);
}

This uses OpenMP for multi-threading. To be compiled with clang++ -std=c++17 -Ofast -march=native -flto -fopenmp file.cpp.
Explanation I tried (please don't use it as a Rust translation guide)
The longest common substring can be found in \$O(n^2)\$ time via dynamic programming. That dynamic programming can be calculated (if the strings are \$s\$ and \$t\$) via the formula $$dp_{i,j} = \begin{cases}dp_{i-1,j-1} + 1&amp; s_i = t_j\\0&amp; \text{otherwise}\end{cases}$$
(and then the answer is just the highest value in \$dp\$). A naive solution would be to iterate over pairs of strings of length \$n\$ (resulting in \$O(4^n n^2)\$ time complexity). However, instead of simply doing that, my program only iterates over all possible values of the first string. Then, it simply does that, but instead of storing a proper dynamic programming array (that wouldn't be possible because there is no second string), it stores an array of all possible rows in it with counters of how many ways exist to reach this row. To calculate the next array of possible rows from the current array of possible rows, my program simply tries all of them with both possible values of the next bit in the second string. This leads to a speedup, because if two prefixes of the second string lead to the same state, they can be &quot;merged&quot; into one execution path.
I suspect this is similar to the optimization from the top answer in a similar challenge but for Levenshtein distance, but the explanation there is so bad I couldn't understand it at all.
The optimization that got this to 21: if at a certain point a possible row is encountered such that all its numbers are too small to ever improve the length of the longest substring in it, it can be directly calculated how much it will add to the answer.
Takes input as a single number from stdin. Outputs 734551/131072 for 13, 392340511/67108864 for 14, 1630366263/268435456 for 15, 6751032665/1073741824 for 16, 6967595579/1073741824 for 17, 114759115773/17179869184 for 18, 235733542633/34359738368 for 19, 1933121200141/27877906944 for 20 and 7912473298597/1099511627776 for 21.