Calculate the average longest common substring exactly [Question inspired by Can you calculate the average Levenshtein distance exactly? . Thank you Anush. ]

The longest common substring between two strings is the longest substring which is common to both.  Please note this is not the same as the longest common subsequence whose fastest algorithm takes quadratic time.

The challenge is to compute the average length of the longest common substring between two independent and uniformly random chosen binary strings of length n each.  Your output must be exact but can be given in any easy to understand human readable form. 

Examples for n = 1..12


1/2
9/8
7/4
295/128
361/128
6741/2048
15217/4096
8389/2048
291431/65536
2500643/524288
2657159/524288
22420789/4194304


Score

Your score is the highest value of  you can reach. I will run your code on my Linux machine for 1 minute and then kill the job to get the score.

I will maintain a leaderboard that shows the best score for each language used in an answer.  

Worked example

Following a request, here is the full set of distances for n = 3. I have not include strings B and A if A and B are already listed. This is because the distance function is symmetric.

000 000 3
000 001 2
000 010 1
000 011 1
000 100 2
000 101 1
000 110 1
000 111 0
001 001 3
001 010 2
001 011 2
001 100 2
001 101 2
001 110 1
001 111 1
010 010 3
010 011 2
010 100 2
010 101 2
010 110 2
010 111 1
011 011 3
011 100 1
011 101 2
011 110 2
011 111 2
100 100 3
100 101 2
100 110 2
100 111 1
101 101 3
101 110 2
101 111 1
110 110 3
110 111 2
111 111 3


Leaderboard


n = 22 in C++ by my pronoun is monicareinstate.
n = 18 in Rust by Plasma_000.
n = 14 in C by Mitchel Spector.
n = 11 in Python with pypy 3 by Alex.
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.