【学习】字符串的各种-SAM

Jacinth posted @ 2016年9月11日 16:45 in Lerning with tags 字符串学习后缀自动机 Learning , 900 阅读

想来SAM也真是太神辣

感觉跳坑里就~~死在里面~~出不来了

所以把它拎出来再学（bian）习（shi）一下

后缀自动机可以被理解为所有子串的简明信息。后缀自动机以压缩后的形式包含了一个长度为n的字符串的所有信息，仅需要O(n)的空间。并且，它能在O(n)时间内被构造。（人家都O(n)了没法无视啊！！！）

SAM 是处理字符串相关问题的有力工具, 可以解决包括但不限于以下问题:

判断W是否为T的子串
判断W是否为T的后缀
计算T的不同子串个数
计算T的不同子串的总长度
计算W在T中的出现次数
查找W在T中第一次出现位置
查找W在T中所有的出现位置
查找T1&T2的最长公共子串
查找T1到Tk的最长公共子串
查找T的最小循环节
查找T的第k小子串
查找最短的不是T的子串的字符串
......

STATE

我们定义

$endpos(T,s)$ 为T中s出现位置终点的集合。且当

$endpos(T,s_1) == endpos(T,s_2)$ 我们就称

$s_1$ 和

$s_2$ 终点等价

我们可以知道，某个状态u，可以识别T的某个子串的集合, 设这个集合为

$substrings(u)$ 而

$substrings(u)$ 中的两个子串都是终点等价的。

考虑对于T的任意两个子串

$s_1,s_2$ 而言，

$endpos(T,s_1),endpos(T,s_2)$ 之间的关系（假设

$length(s_1) \leq length(s_2)$ ）:

若

$endpos(s_1) \cap endpos(s_2) \neq \emptyset$ ，即

$s_1,s_2$ 同时以T的某个字符为结尾，那么

$s_1$ 必为

$s_2$ 的后缀（含

$s_1==s_2$ ）

同时，若

$s_1$ 是

$s_2$ 的后缀，那么

$endpos(s_1) \supseteq endpos(s_2)$ （子串长度越长队endpos的限制越多导致endpos的集合越小），即

$endpos(s_1) \cap endpos(s_2) \neq \emptyset$ 。

所以

$endpos(s_1) \supseteq endpos(s_2) \Leftrightarrow s_1 \sqsupset s_2$

因而我们只剩下了两种状况

$\begin{cases} endpos(s_1) \supseteq endpos(s_2), & \text{if } s_1 \sqsupset s_2 \\ endpos(s_1) \cap endpos(s_2) = \emptyset, & \text{otherwise} \end{cases}$

我们发现由于同一

$substrings(u)$ 下最长子串和最短子串间的endpos相等，则最短子串为最长子串的后缀，对于所有

$substrings(u)$ 下的

$s_i$ 我们可以发现它都是

$substrings(u)$ 的后缀，同样的也都是最长子串的后缀。

所以这就意味这每一个状态都对应一段连续的后缀，（很厉害的样子）

根据之前的内容，对于一个状态u我们可以给出：

$longest(u) : substring(u)$ 中最长的子串
$shortest(u): substring(u)$ 中最短的子串
$maxlen(u): longest(u)$ 的长度
$minlen(u): shortest(u)$ 的长度

而一个状态u可以由以上四个来表示。

SUFFIX LINK

我们给定两个状态 $u,v$ 那么 $v = link(u)$ 即为 $u$ 到 $v$ 的suffix link 且 $maxlen(v) + 1 = minlen(u)$ . suffix link 可以把状态之间用suffix link 连起来

STATE'S TRANSITIONS

我们给定一个状态 $u$ 和标记 $c$ ， $trans(u,c) = v$ 表示状态 $u$ 到状态 $v$ 存在状态转移路径。

我们可以知道以 $v$ 为终点的转移都有一个相同的标记。

令 $U_v = \{ u_i \mid trans(u_i, c) = v \}$

我们之前知道对于一个状态 $v,substring(v)$ 中的子串为连续的，又由于状态 $v$ 的转移都有相同的符号，那么 $\{ s_i \mid s_i \in substrings(u_i), u_i \in U_v \}$ 也必为连续的。

SAM的构造步骤

我们对于SAM中的每个状态，维护以下内容

$maxlen(u)$
$link(u)$
$trans(u,\Sigma)$ [以 $u$ 为起点的状态转移]

构造过程：

新建状态 $np$ ，使 $maxlen(np) = maxlen(last) + 1$
从状态 $last$ 开始沿着suffix-link path访问每个状态，直到 $p = null$ 或存在 $trans(p,T_i)$ ，令 $trans(p,T_i) = np$
判断p是否为null,
- 若 $p = null$ ，则 $link(np) = st, la = np$ 返回第一步
- 否则p为某个存在的状态且trans(p,T_i) = q
  - 若 $maxlen(p)+1 = maxlen(q)$ 则 $link(np) = q, la = np$ 返回第一步
  - 若 $maxlen(p)+1 < maxlen(q)$ 则从 $q$ 状态拆出状态 $nq$ ，令 $link(nq) = link(q) , link(q) = link(np) = nq, la = np$ 返回第一步

萌萌哒的extend代码QAQ:

SAM-extend
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	`void` `extend(int` `xx)` `//mx(p)表示maxlen(p), a[p][xx]表示trans(p,xx), fa[p]表示link(p)` `{` `int` `p = la,np = la = ++tot;` `mx[np] = mx[p]+1;` `while` `(!a[p][xx] && p) a[p][xx] = np, p = fa[p];` `if` `(!p) fa[np] = 1;` `else` `{` `int` `q = a[p][xx];` `if` `(mx[p]+1 == mx[q]) fa[np] = q;` `else` `{` `int` `nq = ++tot;` `mx[nq] = mx[p]+1;` `memcpy(a[nq],a[q],sizeof(a[q]));` `fa[nq] = fa[q], fa[np] = fa[q] = nq;` `while` `(a[p][xx] == q) a[p][xx] = nq, p = fa[p];` `}` `}` `}`

其他信息的维护

minlen(u)
- 有 $v = link(u) \implies maxlen(v) + 1 = minlen(u)$ 直接在更新 $link(u)$ 时更新 $minlen(u)$ 就可以了
first\_endpos(u) 表示 endpos(u)中最小的下标
- 对于状态 $u$ , $endpos(u)$ 的变更伴随着指向状态 $u$ 的suffix-link的建立。所以我们首先维护 $first\_endpos(u)$ ，在后续的过程中，我们只用沿着suffix-link反向DFS可得 $endpos(u)$
- 对于first\_endpos(u)的维护，我们只用
  - 在新建状态 $np$ 时，设 $first\_endpos(np)=i$
  - 在新建状态 $nq$ 时，设 $first\_endpos(nq)=first\_endpos(q)$
accept(u) 表示接收节点
- 我们只用看 $u$ 是否在从 $la$ 到 $st$ 的suffix path上即可。因此我们可以在创建SAM后扫一遍suffix path就可以得到所有的接收状态

似乎to be continued...

各种各样的参考资料：

Suffix Automaton Tutorial （挺详细哒，多看几遍基本能弄懂一点吧qaq，大部分内容来源于此
cls的冬令营讲稿，感觉真是厉害极辣（%%%
后缀自动机与线性构造后缀树 from:fanhq666的博客（%%%
后缀自动机：O(N)的构建及应用某俄文教程的翻译，棒棒哒，有一些用法的介绍

先搬了几道题（无视奇奇怪怪的时间线吧qaq）

BZOJ-3998

Descriprtion	对于一个给定长度为N的字符串，求它的第K小子串是什么。
Input	第一行是一个仅由小写英文字母构成的字符串S 第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。
Output	输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1
Sample Input	aabc 0 3
Sample Output	aab

BZOJ-3998
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cstdlib>` `#include <algorithm>` `#include <cmath>` `#define NN 500050` `#define MM 1000010` `using` `namespace` `std;` `int` `n,t,k;` `char` `ch[NN];` `struct` `SAM` `{` `int` `tot,la,a[MM][30],mx[MM],fa[MM],v[NN],q[MM],val[MM],sum[MM];` `SAM(){ la=++tot;}` `void` `extend(int` `xx)` `{` `int` `p=la,np=la=++tot;` `mx[np]=mx[p]+1,val[np]=1;` `while` `(!a[p][xx] && p) a[p][xx]=np,p=fa[p];` `if` `(!p) fa[np]=1;` `else` `{` `int` `q=a[p][xx];` `if` `(mx[p]+1==mx[q]) fa[np]=q;` `else` `{` `int` `nq=++tot; mx[nq]=mx[p]+1;` `memcpy(a[nq],a[q],sizeof(a[q]));` `fa[nq]=fa[q],fa[np]=fa[q]=nq;` `while` `(a[p][xx]==q) a[p][xx]=nq,p=fa[p];` `}` `}` `}` `void` `pre()` `{` `for` `(int` `i=1;i<=tot;++i) v[mx[i]]++;` `for` `(int` `i=1;i<=n;++i) v[i]+=v[i-1];` `for` `(int` `i=tot;i;i--) q[v[mx[i]]--]=i;` `for` `(int` `i=tot;i;i--)` `{` `int` `tmp=q[i];` `if` `(t==1) val[fa[tmp]]+=val[tmp];` `else` `val[tmp]=1;` `}` `val[1]=0;` `for` `(int` `i=tot;i;i--)` `{` `int` `tmp=q[i]; sum[tmp]=val[tmp];` `for` `(int` `j=0;j<26;++j) sum[tmp]+=sum[a[tmp][j]];` `}` `}` `void` `dfs(int` `xx,int` `yy)` `{` `if` `(yy<=val[xx])` `return;` `yy-=val[xx];` `for` `(int` `i=0;i<26;++i)` `if` `(int` `tmp=a[xx][i])` `{` `if(yy<=sum[tmp])` `{` `putchar(i+'a'); dfs(tmp,yy);` `return;` `}` `yy-=sum[tmp];` `}` `}` `}SAM;` `int` `main()` `{` `scanf("%s",ch+1); n=strlen(ch+1);` `scanf("%d%d",&t,&k);` `for` `(int` `i=1;i<=n;++i) SAM.extend(ch[i]-'a');` `SAM.pre();` `if` `(k>=SAM.sum[1]) {` `puts("-1");` `return` `0;}` `else` `SAM.dfs(1,k);` `return` `0;` `}`

BZOJ-4516: [Sdoi2016]生成魔咒

Descriprtion

求每次操作后不同子串个数

听说有SA的做法飞起来

但是由于在学习SAM就用SAM了呀（明明SAM简单辣

其实更新的时候加上 $len[i]-len[fa[i]]$ 就可以了（板子里是 $mx[i]-mx[fa[i]]$ ）

BZOJ-4516
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41	`#include <bits/stdc++.h>` `using` `namespace` `std;` `typedef` `long` `long` `LL;` `const` `int` `MM = 200010;` `int` `n,x;` `LL ans;` `struct` `Sam` `{` `int` `tot,la,mx[MM],fa[MM],val[MM];` `map <int,int> a[MM];` `Sam() { la = ++tot; }` `void` `extend(int` `xx)` `{` `int` `p = la, np = ++tot; la = np;` `mx[np] = mx[p] + 1, val[np] = 1;` `while` `(!a[p][xx] && p) a[p][xx] = np, p = fa[p];` `if` `(!p) fa[np] = 1;` `else` `{` `int` `q = a[p][xx];` `if` `(mx[p]+1 == mx[q]) fa[np] = q;` `else` `{` `int` `nq = ++tot;` `mx[nq] = mx[p]+1;` `a[nq] = a[q];` `fa[nq] = fa[q] , fa[np] = fa[q] = nq;` `while` `(a[p][xx] == q && p) a[p][xx] = nq, p = fa[p];` `}` `}` `ans += mx[np] - mx[fa[np]];` `printf("%lld\n",ans);` `}` `}SAM;` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d",&x), SAM.extend(x);` `return` `0;` `}`

BZOJ-4566: [Haoi2016]找相同字符

Descriprtion	给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。
Input	两行，两个字符串 $s_1,s_2$ ,长度分别为 $n_1,n_2$ 。 $1 \leq n_1, n_2 \leq 200000$ ，字符串中只有小写字母
Output	输出一个整数表示答案
Sample Input	aabb bbaa
Sample Output	10

每个节点对答案的贡献为 $(mx[x]-mx[fa[x]]) \times sz[0][x] \times sz[1][x]$

BZOJ-4566
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54	`#include <bits/stdc++.h>` `using` `namespace` `std;` `typedef` `long` `long` `LL;` `const` `int` `NN = 200005,MM = 800005;` `int` `mx[MM],a[MM][26],fa[MM],tot=0,pos,la,q[MM],t[MM],sz[2][MM],n1,n2;` `LL ans;` `char` `ch1[NN],ch2[NN];` `inline` `void` `extend(int` `xx)` `{` `int` `p = la, np = la = ++tot;` `mx[np] = mx[p] + 1;` `while` `(!a[p][xx] && p) a[p][xx] = np, p = fa[p];` `if` `(!p) fa[np] = 1;` `else` `{` `int` `q = a[p][xx];` `if` `(mx[p]+1 == mx[q]) fa[np] = q;` `else` `{` `int` `nq = ++tot;` `mx[nq] = mx[p] + 1;` `memcpy(a[nq],a[q],sizeof(a[nq]));` `fa[nq] = fa[q] , fa[np] = fa[q] = nq;` `while` `(a[p][xx] == q && p) a[p][xx] = nq, p = fa[p];` `}` `}` `}` `int` `main()` `{` `scanf("%s",ch1); n1 =` `strlen(ch1);` `scanf("%s",ch2); n2 =` `strlen(ch2);` `la = ++tot;` `int` `p=1;` `for` `(int` `i=0;i<n1;++i)` `{` `extend(ch1[i]-'a');` `p=a[p][ch1[i]-'a']; sz[0][p]++;` `}` `p = la = 1;` `for` `(int` `i=0;i<n2;++i)` `{` `extend(ch2[i]-'a');` `p=a[p][ch2[i]-'a']; sz[1][p]++;` `}` `ans = 0ll;` `for` `(int` `i=1;i<=tot;++i) ++t[mx[i]];` `for` `(int` `i=1;i<=tot;++i) t[i] += t[i-1];` `for` `(int` `i=1;i<=tot;++i) q[t[mx[i]]--] = i;` `for` `(int` `i=tot;i;--i) sz[0][fa[q[i]]] += sz[0][q[i]], sz[1][fa[q[i]]] += sz[1][q[i]];` `for` `(int` `i=1;i<=tot;++i) ans += (LL)(mx[i] - mx[fa[i]]) * sz[0][i] * sz[1][i];` `printf("%lld\n",ans);` `return` `0;` `}`

HDU5343 MZL'S Circle Zhou

Descriprtion

给定两个字符串A,B，分别截取其中的子串X和Y，连接组成X+Y。

求不同的X+Y的方案数。

分别对 $A$ ， $B$ 建立后缀自动机

对 $A$ 进行查找 $X$ ，当 $X$ 的末尾不能接上字符 $i$ ，那么就到 $B$ 中查找所有以i为开头的子串

在两个DAG上DP就可以了【撒花

（答案用unsigned long long存啊啊啊啊，傻逼的我一直死在这里不知道多少次了

HDU-5343
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77	`#include <bits/stdc++.h>` `using` `namespace` `std;` `typedef` `unsigned` `long` `long` `LL;` `const` `int` `NN = 200010;` `char` `ch1[NN],ch2[NN];` `LL dp1[NN],dp2[NN];` `int` `T;` `struct` `SAM` `{` `int` `a[NN][26],mx[NN],la,tot,fa[NN];` `void` `Clr()` `{` `la = tot = 0;` `fa[0] = -1;` `memset(a,-1,sizeof(a));` `mx[0] = 0;` `}` `void` `extend(int` `xx)` `{` `int` `p = la, np = la = ++tot;` `mx[np] = mx[p] + 1;` `while` `(a[p][xx]==-1 && (~p)) a[p][xx] = np, p = fa[p];` `if` `(p == -1) fa[np] = 0;` `else` `{` `int` `q = a[p][xx];` `if` `(mx[p]+1 == mx[q]) fa[np] = q;` `else` `{` `int` `nq = ++tot;` `mx[nq] = mx[p] + 1;` `memcpy(a[nq],a[q],sizeof(a[nq]));` `fa[nq] = fa[q] , fa[np] = fa[q] = nq;` `while` `(a[p][xx] == q && (~p)) a[p][xx] = nq, p = fa[p];` `}` `}` `}` `}A,B;` `LL DFS2(int` `xx)` `{` `if` `(xx == -1)` `return` `0;` `LL &pre = dp2[xx];` `if` `(pre != -1)` `return` `pre;` `pre = 1;` `for` `(int` `i=0;i<26;++i) pre += DFS2(B.a[xx][i]);` `return` `pre;` `}` `LL DFS1(int` `xx)` `{` `LL &pre = dp1[xx];` `if` `(pre != -1)` `return` `pre;` `pre = 1;` `for` `(int` `i=0;i<26;++i)` `{` `if` `(~A.a[xx][i]) pre += DFS1(A.a[xx][i]);` `else` `pre += DFS2(B.a[0][i]);` `}` `return` `pre;` `}` `int` `main()` `{` `scanf("%d",&T);` `for` `(int` `_=1;_<=T;++_)` `{` `A.Clr(), B.Clr();` `scanf("%s%s",ch1,ch2);` `int` `l1 =` `strlen(ch1), l2 =` `strlen(ch2);` `for` `(int` `i=0;i<l1;++i) A.extend(ch1[i]-'a');` `for` `(int` `i=0;i<l2;++i) B.extend(ch2[i]-'a');` `memset(dp1,-1,sizeof(dp1)),` `memset(dp2,-1,sizeof(dp2));` `printf("%llu\n",DFS1(0));` `}` `return` `0;` `}`

BZOJ-4032：[HEOI2015]最短不公共子串

Descriprtion	给两个小写字母串A，B，请你计算： (1) A的一个最短的子串，它不是B的子串 (2) A的一个最短的子串，它不是B的子序列 (3) A的一个最短的子序列，它不是B的子串 (4) A的一个最短的子序列，它不是B的子序列
Input	两行，小写字母表示的字符串A和B
Output	输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1.
Sample Input	aabbcc abcabc
Sample Output	2 4 2 4

四个小问，答案都是最小公共子××+1

感觉非常厉害

对于子串，在建立的后缀自动机上跑匹配

对于子序列，采用DP的贪心来做，la[i][j]表示第i位后第一个j出现的位置

然后用BFS四（fu）合（zhi）一就可以了

BZOJ-4032
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111	`#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `NN = 2001, MM = 4001;` `char` `ch1[NN],ch2[NN];` `int` `l1,l2,la1[NN][26],la2[NN][26],vis[NN][MM],a[MM][26],fa[MM],la=1,tot=1,mx[MM];` `struct` `REC` `{` `int` `x,y,l;}tmp,tmpp;` `queue <REC> que;` `void` `extend(int` `xx)` `{` `int` `p = la,np = la = ++tot;` `mx[np] = mx[p]+1;` `while` `(!a[p][xx] && p) a[p][xx] = np, p = fa[p];` `if` `(!p) fa[np] = 1;` `else` `{` `int` `q = a[p][xx];` `if` `(mx[p]+1 == mx[q]) fa[np] = q;` `else` `{` `int` `nq = ++tot;` `mx[nq] = mx[p]+1;` `memcpy(a[nq],a[q],sizeof(a[q]));` `fa[nq] = fa[q], fa[np] = fa[q] = nq;` `while` `(a[p][xx] == q) a[p][xx] = nq, p = fa[p];` `}` `}` `}` `void` `Clr()` `{` `memset(vis,0,sizeof(vis));` `while` `(!que.empty()) que.pop();` `}` `void` `Solve1()` `{` `Clr();` `for` `(int` `i=0;i<l1;++i) tmp.x = i, tmp.y = 1, tmp.l = 0, que.push(tmp);` `while` `(!que.empty())` `{` `tmp = que.front(); que.pop();` `if` `(tmp.x == l1)` `continue;` `int` `nx = tmp.x +1, ny = a[tmp.y][ch1[nx]-'a'];` `if` `(ny == 0) {` `printf("%d\n",tmp.l+1);` `return; }` `if` `(!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);` `}` `printf("%d\n",-1);` `return;` `}` `void` `Solve2()` `{` `Clr();` `for` `(int` `i=0;i<l1;++i) tmp.x = i, tmp.y = 0, tmp.l = 0, que.push(tmp);` `while` `(!que.empty())` `{` `tmp = que.front(); que.pop();` `if` `(tmp.x == l1)` `continue;` `int` `nx = tmp.x+1, ny = la2[tmp.y][ch1[nx]-'a'];` `if` `(ny == 0x3f3f3f3f) {` `printf("%d\n",tmp.l+1);` `return;}` `if` `(!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);` `}` `printf("%d\n",-1);` `return;` `}` `void` `Solve3()` `{` `Clr(); tmp.x = 0, tmp.y = 1, tmp.l = 0, que.push(tmp);` `while` `(!que.empty())` `{` `tmp = que.front(); que.pop();` `for` `(int` `i=0;i<26;++i)` `{` `int` `nx = la1[tmp.x][i];` `if` `(nx == 0x3f3f3f3f)` `continue;` `int` `ny = a[tmp.y][ch1[nx]-'a'];` `if` `(ny == 0) {` `printf("%d\n",tmp.l+1);` `return;}` `if` `(!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);` `}` `}` `printf("%d\n",-1);` `return;` `}` `void` `Solve4()` `{` `Clr(); tmp.x = 0, tmp.y = 0, tmp.l = 0, que.push(tmp);` `while` `(!que.empty())` `{` `tmp = que.front(); que.pop();` `for` `(int` `i=0;i<26;++i)` `{` `int` `nx = la1[tmp.x][i], ny = la2[tmp.y][i];` `if` `(nx == 0x3f3f3f3f)` `continue;` `if` `(ny == 0x3f3f3f3f) {` `printf("%d\n",tmp.l+1);` `return;}` `if` `(!vis[nx][ny]) vis[nx][ny] = 1, tmpp.x = nx, tmpp.y = ny, tmpp.l = tmp.l+1, que.push(tmpp);` `}` `}` `printf("%d\n",-1);` `return;` `}` `int` `main()` `{` `scanf("%s%s",ch1+1,ch2+1);` `l1 =` `strlen(ch1+1), l2 =` `strlen(ch2+1);` `for` `(int` `i=1;i<=l2;++i) extend(ch2[i]-'a');` `memset(la1,0x3f,sizeof(la1)),` `memset(la2,0x3f,sizeof(la2));` `for` `(int` `i=0;i<=l1;++i)` `for` `(int` `j=i+1;j<=l1;++j)` `la1[i][ch1[j]-'a'] = min(j,la1[i][ch1[j]-'a']);` `for` `(int` `i=0;i<=l2;++i)` `for` `(int` `j=i+1;j<=l2;++j)` `la2[i][ch2[j]-'a'] = min(j,la2[i][ch2[j]-'a']);` `Solve1(), Solve2(), Solve3(), Solve4();` `return` `0;` `}`

BZOJ-3238: [Ahoi2013]差异

我们需要一个后缀树，然后两个后缀的lcp就是它们lca的len，我们在后缀树上进行DP就可以了。

后缀树呢我们可以通过反序后缀自动机得到。

BZOJ-3238
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57	`#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `NN = 1000010;` `typedef` `long` `long` `LL;` `int` `val[NN],fa[NN],a[NN][27],mx[NN],tot=1,cnt,head[NN],la=1,len;` `LL ans;` `struct` `E` `{` `int` `ne,v;` `}e[NN];` `inline` `void` `extend(int` `xx)` `{` `int` `p = la, np = la = ++tot;` `mx[np] = mx[p] + 1, val[np] = 1;` `while` `(!a[p][xx] && p) a[p][xx] = np, p = fa[p];` `if` `(!p) fa[np] = 1;` `else` `{` `int` `q = a[p][xx];` `if` `(mx[p]+1 == mx[q]) fa[np] = q;` `else` `{` `int` `nq = ++tot;` `mx[nq] = mx[p] + 1;` `memcpy(a[nq],a[q],sizeof(a[nq]));` `fa[nq] = fa[q] , fa[np] = fa[q] = nq;` `while` `(a[p][xx] == q && p) a[p][xx] = nq, p = fa[p];` `}` `}` `}` `void` `Build(int` `xx,int` `yy)` `{` `e[++cnt].ne = head[xx], head[xx] = cnt, e[cnt].v = yy;` `}` `void` `DP(int` `xx,int` `p)` `{` `for` `(int` `i=head[xx];i;i=e[i].ne)` `{` `DP(e[i].v,xx);` `val[xx] += val[e[i].v];` `}` `mx[xx] -= mx[p];` `ans -= (LL)val[xx] * (val[xx]-1) * mx[xx];` `}` `char` `ch[NN];` `int` `main()` `{` `scanf("%s",ch);` `len =` `strlen(ch);` `for` `(int` `i=len-1;i>=0;--i) extend(ch[i]-'a');` `ans = (LL) (len-1) * len * (len+1) >> 1ll;` `for` `(int` `i=2;i<=tot;++i) Build(fa[i],i);` `for` `(int` `i=head[1];i;i=e[i].ne) DP(e[i].v,1);` `printf("%lld\n",ans);` `return` `0;` `}`

BZOJ-3926

神奇的题目描述啊。。。感觉语文不好的后果来了

ZJOI的题目呢。。。马上省选了好虚。。强省蒟蒻滚粗无疑辣。。

BZOJ-3926
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74	`#include <iostream>` `#include <cstdio>` `#include <cstdlib>` `#include <cmath>` `#include <cstring>` `#include <algorithm>` `#include <string>` `#define LL long long` `#define MM 4000005` `#define NN 100005` `using` `namespace` `std;` `LL ans;` `int` `n,c,cc[NN],d[NN],tot=0,head[NN];` `struct` `Edge` `{` `int` `ne,v;` `}e[NN<<1];` `void` `Build(int` `xx,int` `yy)` `{` `e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy;` `e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx;` `}` `struct` `SAM` `{` `int` `cnt,fa[MM],a[MM][10],mx[MM];` `SAM(){cnt=1;}` `int` `extend(int` `p,int` `c)` `{` `int` `np=++cnt; mx[np]=mx[p]+1;` `while` `(!a[p][c] && p) a[p][c]=np, p=fa[p];` `if` `(!p) fa[np]=1;` `else` `{` `int` `q=a[p][c];` `if` `(mx[p]+1==mx[q]) fa[np]=q;` `else` `{` `int` `nq=++cnt;mx[nq]=mx[p]+1;` `memcpy(a[nq],a[q],sizeof(a[q]));` `fa[nq]=fa[q], fa[np]=fa[q]=nq;` `while` `(a[p][c]==q) a[p][c]=nq, p=fa[p];` `}` `}` `return` `np;` `}` `void` `solve()` `{` `for` `(int` `i=1;i<=cnt;++i) ans+=mx[i]-mx[fa[i]];` `}` `}Sam;` `void` `DFS(int` `x,int` `fa,int` `p)` `{` `int` `t=Sam.extend(p,cc[x]);` `for` `(int` `i=head[x];i;i=e[i].ne)` `if` `(e[i].v!=fa)` `DFS(e[i].v,x,t);` `}` `int` `main()` `{` `scanf("%d%d",&n,&c);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d",&cc[i]);` `int` `x,y;` `for` `(int` `i=1;i<n;++i)` `{` `scanf("%d%d",&x,&y);` `Build(x,y);` `d[x]++, d[y]++;` `}` `for` `(int` `i=1;i<=n;++i)` `if` `(d[i]==1) DFS(i,0,1);` `Sam.solve();` `printf("%lld\n",ans);` `return` `0;` `}`

BZOJ-4199

唔。。2015年的NOI题目呢。。。别忘了考虑负数。。

BZOJ-4199
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100	`#include <iostream>` `#include <cstdio>` `#include <cstring>` `#include <cmath>` `#include <cstdlib>` `#include <algorithm>` `#define LL long long` `#define NN 600006` `#define INF 2e18` `using` `namespace` `std;` `LL mav[NN],ma1[NN],ma2[NN],mi1[NN],mi2[NN],head[NN],n,m,a[NN],size[NN],ans[NN],tot=0;` `bool` `vis[NN];` `char` `ch[NN];` `struct` `Edge` `{` `int` `v,ne,w;` `}e[NN];` `void` `Build(LL xx,LL yy,LL zz)` `{` `e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;` `}` `struct` `SAM` `{` `LL cnt,la,ne[NN][26],fa[NN],mx[NN],t[NN],now,tmp,nx[NN];` `SAM(){la=++cnt;}` `void` `extend(int` `xx)` `{` `LL p=la,np=la=++cnt,c=ch[xx]-'a';` `mx[np]=mx[p]+1, t[np]=xx;` `while` `(!ne[p][c] && p) ne[p][c]=np, p=fa[p];` `if` `(!p) fa[np]=1;` `else` `{` `LL q=ne[p][c];` `if` `(mx[p]+1==mx[q]) fa[np]=q;` `else` `{` `LL nq=++cnt; mx[nq]=mx[p]+1;` `memcpy(ne[nq],ne[q],sizeof(ne[q]));` `fa[nq]=fa[q], fa[np]=fa[q]=nq;` `while` `(ne[p][c]==q) ne[p][c]=nq, p=fa[p];` `}` `}` `}` `void` `DFS(LL xx,LL h)` `{` `if` `(t[xx]) ma1[xx]=mi1[xx]=a[t[xx]], size[xx]=1;` `else` `ma1[xx]=-INF,mi1[xx]=INF, size[xx]=0;` `ma2[xx]=-INF, mi2[xx]=INF;` `for` `(LL i=head[xx];i;i=e[i].ne)` `{` `LL yy=e[i].v;` `DFS(yy,h+e[i].w);` `if` `(ma1[yy]>ma1[xx])` `{` `ma2[xx]=ma1[xx], ma1[xx]=ma1[yy];` `if` `(ma2[yy]>ma2[xx]) ma2[xx]=ma2[yy];` `}` `else` `if` `(ma1[yy]>ma2[xx]) ma2[xx]=ma1[yy];` `if` `(mi1[yy]<mi1[xx])` `{` `mi2[xx]=mi1[xx], mi1[xx]=mi1[yy];` `if` `(mi2[yy]<mi2[xx]) mi2[xx]=mi2[yy];` `}` `else` `if` `(mi1[yy]<mi2[xx]) mi2[xx]=mi1[yy];` `size[xx]+=size[yy], nx[xx]+=nx[yy];` `}` `now=-INF; tmp=(size[xx](size[xx]-1))/2;` `if` `(size[xx]>=4)now=max(max(ma1[xx]ma2[xx],mi1[xx]mi2[xx]),max(ma1[xx]mi2[xx],ma2[xx]mi1[xx]));` `else` `if` `(size[xx]>=3) now=max(max(ma1[xx]ma2[xx],mi1[xx]mi2[xx]),ma1[xx]mi1[xx]);` `else` `if` `(size[xx]>=2) now=ma1[xx]*ma2[xx];` `if` `(now!=INF) ans[h]+=tmp-nx[xx], mav[h]=max(mav[h],now);` `nx[xx]+=tmp-nx[xx];` `}` `}Sam;` `int` `main()` `{` `scanf("%lld",&n);` `scanf("%s",ch+1);` `for` `(LL i=n;i;i--) Sam.extend(i);` `vis[1]=1;` `for` `(LL i=1;i<=Sam.cnt;++i)` `if` `(Sam.t[i]&&!vis[i])` `for` `(LL j=i;!vis[j];vis[j]=1,j=Sam.fa[j]) Build(Sam.fa[j],j,Sam.mx[j]-Sam.mx[Sam.fa[j]]);` `for` `(LL i=0;i<=n;++i) mav[i]=-INF;` `for` `(LL i=1;i<=n;++i)` `scanf("%lld",&a[i]);` `Sam.DFS(1,0);` `for` `(LL i=n-1;i>=0;--i) ans[i]=ans[i]+ans[i+1], mav[i]=max(mav[i],mav[i+1]);` `for` `(LL i=0;i<n;++i)` `{` `if` `(mav[i]==-INF) mav[i]=0;` `printf("%lld %lld\n",ans[i],mav[i]);` `}` `return` `0;` `}<span style="white-space: normal;">` `</span>`

[回复]

PSEB 10th Class Ques 说:
2022年9月05日 12:50

Punjab School Education Board came into Existence Through a Legislative Enactment in November 1969 for the Development and Promotion of School Education in the state of Punjab. PSEB is Going to Conduct PSEB 10th Class Question Paper the Matric Examination month of March to April 2023 under Punjab State Government. PSEB is published in the Matric Exam Model Question Paper 2023 Blueprint at Official Website

Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍