Question

字符串的5、串接子串

Answer 1

“串接”是 Σ* 上的重要二元运算。对于 Σ* 中的两个字符串 s 和 t，它们的串接被定义为在 s 中的字符序列之后跟随着 t 中的字符序列，并被指示为 st。例如，Σ = {a, b, …, z}，并且 s = bear 且 t = hug，则 st = bearhug 而 ts = hugbear。
字符串串接是结合性的，但非交换性运算。空串充当单位；对于任何字符串 s，有 εs = sε = s。所以，集合 Σ* 和串接运算形成了幺半群，就是从 Σ 生成的自由幺半群。此外，长度函数定义从 Σ* 到非负整数的幺半群同态。
字符串 s 被称为是字符串 t 的“子串”或“因子”，如果存在(可能为空)字符串 u 和 v 使得 t = usv。“是其子串”关系定义了在 Σ* 上的偏序，其最小元是空串。