Haskell实现字符串按长度n滑动分割，用于德布鲁因序列验证

嘿，作为Haskell新手，想要搞定德布鲁因序列的验证其实没那么复杂，咱们一步步来拆解，先从你提到的滑动生成n长子串开始，再讲完整的验证逻辑，最后给你一些额外的思路参考～

第一步：生成滑动n长子串 #

要得到所有长度为n的滑动子串，Haskell的Data.List模块里的tails函数可以帮大忙——它能生成字符串的所有后缀。比如对"011001100"，tails会返回：

["011001100", "11001100", "1001100", "001100", "01100", "1100", "100", "00", "0"]

接下来我们只需要对每个后缀取前n个字符，再通过计算数量直接截断（避免处理长度不足n的后缀）。写个函数实现这个逻辑：

import Data.List (tails)

-- 生成所有长度为n的滑动子串
slidingSubstrings :: Int -> String -> [String]
slidingSubstrings n s = take (length s - n + 1) $ map (take n) (tails s)

比如你给的例子，输入slidingSubstrings 3 "011001100"会得到：
["011","110","100","001","011","110","100"]（这里你之前的例子少写了一个"011"，实际应该是7个哦）

第二步：验证是否为德布鲁因序列 #

德布鲁因序列B(k,n)的核心性质是：它包含所有k^n种可能的n长度子串，且每个子串仅出现一次（线性德布鲁因序列的长度是k^n + n -1，对应滑动子串数量刚好是k^n）。基于这个性质，我们可以写出验证函数：

import Data.List (tails, nub)

isDeBruijn :: Int -> String -> Bool
isDeBruijn n s =
  let uniqueChars = nub s       -- 提取字符串中的所有唯一字符，确定字符集
      k = length uniqueChars    -- 字符集的大小k
      expectedSubstringCount = k ^ n  -- 应该包含的子串总数
      substrings = slidingSubstrings n s
  in  -- 两个核心条件：子串数量符合预期，且所有子串都唯一
      length substrings == expectedSubstringCount 
      && length (nub substrings) == expectedSubstringCount

逻辑解释： #

1. nub s会去掉字符串中的重复字符，帮我们确定字符集的大小k（比如二元序列的k=2）。
2. k^n是德布鲁因序列必须覆盖的所有n长度子串的总数。
3. 检查生成的子串数量是否等于k^n（确保序列长度符合德布鲁因的要求），同时检查去重后的子串数量和原数量一致（确保没有重复子串）。

其他实现思路 #

如果你想探索更进阶的方法，可以结合德布鲁因序列的图论背景：

• 德布鲁因序列本质是德布鲁因图中的欧拉回路：每个节点是长度为n-1的字符串，每条边代表添加一个字符得到长度为n的子串。验证时可以模拟这个图的遍历，检查是否能覆盖所有边且不重复，但这个方法对新手来说稍复杂，适合后续深入学习时尝试。

另外，如果你需要处理循环德布鲁因序列（即序列是循环的，最后n-1个字符和开头n-1个字符组成的子串也需要被考虑），可以在生成子串前，把序列的前n-1个字符拼到末尾，再生成子串进行验证。

内容的提问来源于stack exchange，提问作者Mathis Panzani