From 4ac49ead19ffb945d6cedffea5970a92cad98cf9 Mon Sep 17 00:00:00 2001 From: Ir1dXD Date: Mon, 5 Nov 2018 23:18:56 +0800 Subject: [PATCH] Update sam.md --- docs/string/sam.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/docs/string/sam.md b/docs/string/sam.md index 60da231a..62c86f52 100644 --- a/docs/string/sam.md +++ b/docs/string/sam.md @@ -157,7 +157,7 @@ $$ - 令 $last$ 为对应添加字符 $c$ 之前的整个字符串（一开始我们设置 $last=0$ 且我们会在算法的最后一步对应地更新 $last$）。 - 创建一个新的状态 $cur$，并将 $len(cur)$ 赋值为 $len(last)+1$，在这时 $link(cur)$ 的值还未知。 - 现在我们按以下流程进行：我们从状态 $last$ 开始。如果还没有到字符 $c$ 的转移，我们就添加一个到状态 $cur$ 的转移，遍历后缀链接。如果在某个点已经存在到字符 $c$ 的后缀链接，我们就停下来，并将这个状态标记为 $p$。 -- 如果没有找到这样的状态 $p$，我们就到达了虚拟状态 $-1$，我们将 $link(cur)$ 赋值为 $-1$ 并退出。 +- 如果没有找到这样的状态 $p$，我们就到达了虚拟状态 $-1$，我们将 $link(cur)$ 赋值为 $0$ 并退出。 - 假设现在我们找到了一个状态 $p$，其可以转移到字符 $c$，我们将这个状态转移到的状态标记为 $q$。 - 现在我们分类讨论两种状态，要么 $len(p) + 1 = len(q)$，要么不是。 - 如果 $len(p)+1=len(q)$，我们只要将 $link(cur)$ 赋值为 $q$ 并退出。 -- 2.11.0