2025-09-06：字典序最小的生成字符串用go语言，给定两个字符串

摘要：2025-09-06：字典序最小的生成字符串。用go语言，给定两个字符串 str1（长度为 n）和 str2（长度为 m）。我们要构造一个长度为 n + m − 1 的字符串 word，并且对每个下标 i（0 ≤ i ≤ n−1）都要满足一个约束：

2025-09-06：字典序最小的生成字符串。用go语言，给定两个字符串 str1（长度为 n）和 str2（长度为 m）。我们要构造一个长度为 n + m − 1 的字符串 word，并且对每个下标 i（0 ≤ i ≤ n−1）都要满足一个约束：

• 当 str1[i] 为字符 'T' 时，word 从位置 i 开始、长度为 m 的连续片段必须与 str2 完全相同；

• 当 str1[i] 为字符 'F' 时，word 从位置 i 开始、长度为 m 的连续片段必须与 str2 不相同。

在满足上述所有约束的前提下，返回按字典序最小的那个 word；若没有任何字符串能满足这些条件，则返回空串 ""。字典序比较按常规字母表顺序进行：先比较第一个不同字符，字符更靠前的字符串更小；若一个字符串是另一个的前缀，则较短者更小。子串指字符串中连续的一段字符。

str1 仅由 'T' 或 'F' 组成。

str2 仅由小写英文字母组成。

输入: str1 = "TFTF", str2 = "ab"。

输出: "ababa"。

解释:

下表展示了字符串 "ababa" 的生成过程：

下标T/F长度为 m 的子字符串0'T'"ab"1'F'"ba"2'T'"ab"3'F'"ba"

字符串 "ababa" 和 "ababb" 都可以由 str1 和 str2 生成。

返回 "ababa"，因为它的字典序更小。

题目来自力扣3474。

• 创建一个长度为 n + m - 1 的字节数组 ans，初始时每个字符都是 '?'（表示待定位置）。

• 遍历 str1，对于每个 'T' 的位置 i：

找到前一个 'T' 出现的位置 pre（初始为 -m），计算重叠部分的大小 size = max(pre + m - i, 0)。这表示当前 'T' 要求的子串与前一个 'T' 要求的子串有 size 个字符的重叠。检查 str2 的长为 size 的前缀和后缀是否相同（使用 Z 函数计算 str2 的 z 数组，检查 z[m - size] 是否等于 size）。如果不相同，则无法满足约束，返回空串。将 str2 从索引 size 开始的部分复制到 ans 中从 i + size 开始的位置（即填充非重叠部分）。

• 这样，所有 'T' 约束要求的子串都被正确填充（重叠部分已验证，非重叠部分直接复制）。

• 创建一个数组 preQ，记录每个位置之前（包括自身）最近的待定位置（即 ans 中值为 '?' 的位置）的索引。

• 同时，将所有待定位置初始化为 'a'（字典序最小）。

• 再次使用 Z 函数，计算 str2 + ans 的 Z 数组（用于快速判断任意位置开始的子串是否等于 str2）。

• 遍历 str1，对于每个 'F' 的位置 i：

检查从 i 开始的子串是否等于 str2（通过 Z 数组：z[m + i] >= m 表示相等）。如果相等，则需要修改待定位置来破坏匹配。找到子串 ans[i : i+m] 中最后一个待定位置 j（通过 preQ[i+m-1] 获取）。如果没有待定位置（j 将 ans[j] 改为 'b'（因为 'a' 已经不能避免匹配，所以改为稍大的字符，但字典序仍尽量小），并跳过后续检查（直接让 i = j，避免重复修改同一区域）。

• 这样，每个 'F' 约束要求的子串都不等于 str2（通过修改最后一个待定位置为 'b' 来破坏匹配）。

• 如果所有约束都满足，返回 ans 转换后的字符串；否则返回空串。

• 时间复杂度：

计算 Z 函数：每次计算的时间复杂度为 O(|字符串长度|)。这里计算了两次 Z 函数：一次用于 str2（长度为 m），一次用于 str2 + ans（长度为 m + (n+m-1) = n+2m-1）。由于 m 处理 'T' 约束：遍历 str1 的 'T' 位置，每次操作是常数时间（除了复制操作，但复制总长度不超过 n+m），所以为 O(n)。预处理待定位置：遍历 ans（长度为 n+m-1），O(n+m)。处理 'F' 约束：遍历 str1 的 'F' 位置，每次检查 Z 数组是常数时间，修改待定位置也是常数时间，所以为 O(n)。总体时间复杂度为 O(n + m)。

• 额外空间复杂度：

package mainimport ( "bytes" "fmt")func calcZ(s string) int { n := len(s) z := make(int, n) boxL, boxR := 0, 0// z-box 左右边界（闭区间） for i := 1; i 0 && z[m-size]

# -*-coding:utf-8-*-def calc_z(s): n = len(s) z = [0] * n box_l, box_r = 0, 0 for i in range(1, n): if i 0 and z_t[m - size] = m: # 需要修改最后一个待定位置 j = pre_q[i + m - 1] if j