Rt, 本人在阅读 OI-wiki 构建 SAM 代码时不理解（解释看不懂呀qwq），代码如下：

void sam_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}

1. clone 具体代表什么？

   • 我理解这里处理的是，将 $s\cdot c$ 最长的在 $s$ 中出现的后缀设为 $z$，将 $z$ 所处的等价类分裂成两个，clone 应当是其中一个，但 $len[clone]$ 为何是 $len[p]+1$？

2. 为何将所有 $next[c]$ 指向 $q$ 的 $next$ 都转为指向 $clone$？

• 我理解不是应当讨论长度，长度较大的一部分指向分裂出长度较大的状态吗？

  求问，感激不尽！