From 8a6d90359679af8daf2292a97a0d985527733727 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Fri, 13 Sep 2019 22:27:26 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/string/seq-automaton.md | 40 ++++++++++++++++++++-------------------- 1 file changed, 20 insertions(+), 20 deletions(-) diff --git a/docs/string/seq-automaton.md b/docs/string/seq-automaton.md index 08d37715..69d57093 100644 --- a/docs/string/seq-automaton.md +++ b/docs/string/seq-automaton.md @@ -45,7 +45,7 @@ $$ ## 例题 -### "[「HEOI2015」最短不公共子串](https://www.luogu.org/problem/P4112)" +### " [「HEOI2015」最短不公共子串](https://www.luogu.org/problem/P4112) " 这题的 (1) 和 (3) 两问需要后缀自动机,而且做法类似,在这里只讲解 (2) 和 (4) 两问。 @@ -53,9 +53,9 @@ $$ (4) 需要 DP。令 $f(i, j)$ 表示在 A 的序列自动机中处于状态 $i$ ,在 B 的序列自动机中处于状态 $j$ ,需要再添加多少个字符能够不是公共子序列。 -$f(i, null)=0$ + $f(i, null)=0$ -$f(i, j)=\min\limits_{\delta_A(i,c)\ne null}f(\delta_A(i, c), \delta_B(j, c))$ + $f(i, j)=\min\limits_{\delta_A(i,c)\ne null}f(\delta_A(i, c), \delta_B(j, c))$ ??? note "整道题的参考代码" ```cpp @@ -105,29 +105,29 @@ $f(i, j)=\min\limits_{\delta_A(i,c)\ne null}f(\delta_A(i, c), \delta_B(j, c))$ int main() { scanf("%s%s", s + 1, t + 1); - + n = strlen(s + 1); m = strlen(t + 1); - + for (int i = 1; i <= n; ++i) a[i] = s[i] - 'a'; for (int i = 1; i <= m; ++i) b[i] = t[i] - 'a'; - + for (int i = 1; i <= m; ++i) insert(b[i]); - + for (int i = 0; i < 26; ++i) nxt[i] = n + 1; for (int i = n; i >= 0; --i) { memcpy(na[i], nxt, sizeof(nxt)); nxt[a[i]] = i; } - + for (int i = 0; i < 26; ++i) nxt[i] = m + 1; for (int i = m; i >= 0; --i) { memcpy(nb[i], nxt, sizeof(nxt)); nxt[b[i]] = i; } - + int ans = N; - + for (int l = 1; l <= n; ++l) { for (int r = l, u = 1; r <= n; ++r) { u = sam[u].ch[a[r]]; @@ -137,11 +137,11 @@ $f(i, j)=\min\limits_{\delta_A(i,c)\ne null}f(\delta_A(i, c), \delta_B(j, c))$ } } } - + printf("%d\n", ans == N ? -1 : ans); - + ans = N; - + for (int l = 1; l <= n; ++l) { for (int r = l, u = 0; r <= n; ++r) { u = nb[u][a[r]]; @@ -151,9 +151,9 @@ $f(i, j)=\min\limits_{\delta_A(i,c)\ne null}f(\delta_A(i, c), \delta_B(j, c))$ } } } - + printf("%d\n", ans == N ? -1 : ans); - + for (int i = n; i >= 0; --i) { for (int j = 1; j <= tot; ++j) { f[i][j] = N; @@ -164,11 +164,11 @@ $f(i, j)=\min\limits_{\delta_A(i,c)\ne null}f(\delta_A(i, c), \delta_B(j, c))$ } } } - + printf("%d\n", f[0][1] == N ? -1 : f[0][1]); - + memset(f, 0, sizeof(f)); - + for (int i = n; i >= 0; --i) { for (int j = 0; j <= m; ++j) { f[i][j] = N; @@ -179,9 +179,9 @@ $f(i, j)=\min\limits_{\delta_A(i,c)\ne null}f(\delta_A(i, c), \delta_B(j, c))$ } } } - + printf("%d\n", f[0][0] == N ? -1 : f[0][0]); - + return 0; } ``` -- 2.11.0