分类： 算法

发布于

Z函数

Z函数\(Z_i\)表示了在一个字符串\(S\)中，由第\(i\)个字符开始的后缀和整个串的最长公共前缀的长度。
至于\(Z_0\)的值其实没有意义，可以设成\(0\)或是\(n\)。下文令\(Z_0=0\)。

下文中的下标都从零开始。

继续阅读“Z函数”

发布于

后缀自动机

后缀自动机（Suffix Automation, SAM）是一种能够接受所有源串后缀的最简的DFA（确定性有限状态自动机）．他的定义使得他具有以下性质：

  • 最简
  • 是一个有向无环图（DAG），点之间的单向边即为字符的转移
  • 有且仅有源串的所有子串可以在这张图上走到一个节点，一个节点可能对应多个子串，这些子串的各个结束位置均完全一致
    （这些字符串接下来的任何转移均完全相同．为了最简，这些状态会被合并）
  • 时间、空间复杂度均在\(O(n)\)级别（这个需要证明）

继续阅读“后缀自动机”

发布于

积性函数和莫比乌斯反演

您也可以阅读体验更好、叙述更严谨的论文。

积性函数

数论函数是指定义域在正整数、而值域在复数域上的一类函数，即\(f:\mathbb{Z}^{+}\rightarrow\mathbb{C}\)。

下文中的数论函数值域都在整数上。积性函数是一种特殊的数论函数，他们满足对于任意互质的一对数\(p,q\)，有\(f(p)\cdot f(q)=f(pq)\)，即他们的函数值乘起来等于他们乘起来的函数值。特别地，如果对于任意不互质两数上面的条件也成立，则称这个函数为完全积性函数。

继续阅读“积性函数和莫比乌斯反演”