string - 加速计算字母表中没有长度 > 1 的重复子串的字符串数

Question

因此，似乎没有人知道关于大小为 N 的字母表中没有长度 >= 2 的重复子串的字符串数量的 N 公式。De Bruijn 序列的数量可用于提供下限。但是，如果我们想计算尽可能大的 N 的确切数字怎么办？是否有编程技巧(对称性等)可用于计算适当大小的 N 的此类字符串的数量？

Answer 1

要利用的明显对称性是排列字母身份以仅生成按字典顺序排列的最小代表。以下 Python 代码使用带修剪的递归搜索。它不会走得太远，所以我不确定您是否认为它是“蛮力”。

可能会有 Elixir 在等待，但我怀疑不会，在这种情况下，插入 N 就像用石锤挖隧道一样。

import math

def nonrep(n, s=''):
    a = (ord(min(s)) if s else ord('a'))
    c = ((ord(max(s)) + 1) if s else a)
    total = (math.factorial(n) // math.factorial((n - (c - a))))
    for b in range(a, min((c + 1), (a + n))):
        t = (s + chr(b))
        if (t[(- 2):] not in s):
            total += nonrep(n, t)
    return total
for k in range(1, 12):
    print(nonrep(k))

下一步是通过使用过的子字符串进行内存。以下 C++11 代码可以在具有大量内存的机器上相当快地执行 N=6 (2131886084545954033)。

#include <cstdio>
#include <unordered_map>

namespace {

static const int kN(6);

long long Count(std::unordered_map<unsigned long long, long long>* memo,
                unsigned long long used,
                int end) {
  auto got(memo->find(used));
  if (got != memo->end()) {
    return got->second;
  }
  long long total(1);
  for (int j(0); j != kN; ++j) {
    unsigned long long bit(1ULL << (j * kN + end));
    if (used < (1ULL << (j * kN)) && j != 0) {
      total += (kN - j) * Count(memo, used | bit, j);
      break;
    } else if ((used & bit) == 0) {
      total += Count(memo, used | bit, j);
    }
  }
  if (total >= 100) {
    (*memo)[used] = total;
  }
  return total;
}
}  // namespace

int main(void) {
  std::unordered_map<unsigned long long, long long> memo;
  std::printf("%lld\n", 1 + kN * Count(&memo, 0, 0));
}

这之后的下一步可能是更多的对称性破缺，例如，通过智能地排列字母以进一步规范used，但我认为要达到 N=7 还有很长的路要走。