后缀自动机

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

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

继续阅读“后缀自动机”

积性函数和莫比乌斯反演

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

积性函数

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

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

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