史上全网最清晰后缀自动机学习（六）后缀自动机杂题
- 2020 年 2 月 17 日
- 笔记
缘起
后缀自动机系列最后一发——后缀自动机和博弈的小综合~ hihocoder #1466 : 后缀自动机六·重复旋律9
分析
时间限制:10000ms 单点时限:2000ms 内存限制:256MB 描述 小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段字符构成的字符串。 现在小Hi已经不满足于单单演奏了！他通过向一位造诣很高的前辈请教，通过几周时间学习了创作钢琴曲的基本理 论，并开始对曲目做改编或者原创。两个月后，小Hi决定和前辈进行一场创作曲目的较量 规则是这样的，有两部已知经典的作品，我们称之为A和B。经典之所以成为经典，必有其经典之处。 刚开始，纸上会有一段A的旋律和一段B的旋律。两人较量的方式是轮流操作，每次操作可以选择在纸上其中一段旋律 的末尾添加一个音符，并且要求添加完后的旋律依然是所在作品的旋律（也就是A或B的一个子串）。谁词穷了（无法 进行操作）就输了。 小Hi和前辈都足够聪明，但是小Hi还是太年轻，前辈打算教训他一顿。前辈表示会和小Hi进行K次较量，只要小Hi赢 了哪怕一次就算小Hi获得最终胜利。但是前提是开始纸上的两段旋律需要他定。小Hi欣然同意，并且表示每次较量都 让前辈先操作。 前辈老谋深算，显然是有备而来。他已经洞悉了所有先手必胜的初始(两段)旋律。第i天前辈会挑选字典序第i小的初 始(两段)旋律来和小Hi较量。那么问题来了，作为吃瓜群众的你想知道，最后一天即第K天，前辈会定哪两个旋律 呢？ 初始时两段旋律的字典序比较方式是先比较前一个旋律字典序，一样大则比较后一旋律的字典序。 输入 第一行包含一个正整数，K。K<=10^18 第二行包含一个非空的仅有小写字母构成的字符串，表示作品A。|A|<=10^5 第三行包含一个非空的仅有小写字母构成的字符串，表示作品B。|B|<=10^5 输出 输出共两行，每行一个字符串（可能为空），表示答案。 如果无解则只输出一行"NO"。 样例输入 5 ab cd 样例输出 a cd
首先, 对于样例数据, 前辈只有10种必胜策略,按照字典序升序排序为 ("", "c"), ("", "cd"), ("", "d"), ("a", ""), ("a", "cd”),("a","d"),("ab",""), ("ab", "c"), ("b",""), ("b","c"), 所以答案是 a cd
根据我们对SAM的学习, 知道在一个子串后面接上一个字符的含义其实是在SAM上按照trans进行转移. 所以我们就把本题的拼接字符转换成了在A或者B的SAM上进行根据trans进行跳转. 而题目中的一场较量其实就是给你两张DAG（A和B的SAM）, 然后这两张DAG上分别有一枚棋子. 两个玩家轮流选定一张DAG移动这张DAG上的棋子. 不能继续移动者为失败. 这不就是经典的 DAG上博弈的问题么? 使用SG定理予以解决. sg值是博弈论中SG函数的内容, 不懂的童鞋可以去百度学习一下SG函数的内容.
所以和【1】、【2】、【3】相比, 本题每个SAM的节点上要维护的东西发生了变化——要维护的是"sg值"
求出每个SAM节点上的sg值只能解决如下问题
给定两个A、B中的子串, 然后按照题目中的规则拼接字符, 计算谁必胜.
因为一旦给定两个子串, 我们就可以按照SAM的trans进行跳转, 找到DAG上的博弈游戏的初始状态. 然后计算此情形的sg值, 根据sg值是否非零判断先手（前辈）是否必胜.
但是还不够, 因为**本题是求字典序第k小的先手必胜初始状态（下面简称 先手必胜初始状态 为 必胜态）. ** 这是一个挺棘手的问题~
以 A="ab", B="cd"，K=5为例来说明整个过程. 假设我们已经将SAM上每个节点的sg值已经求出来了.
记 A的子串为sA, B的子串为sB. 那么最暴力的想法是把所有必胜态(sA,sB)都求出来然后字典序升序排序然后取第k个不就好了? 而我们想想看这些必胜态需要满足什么性质? 根据SG定理, 就是sg(sA所在节点) != sg(sB所在节点). 为了方便, 记sgA为A的SAM上的sg函数, sgB为B的SAM上的sg函数.
为了后续讲解方便, 我们
令cntA[prefix][x]是以prefix为前缀, 并且sgA值为x的A的子串个数. 同理定义 cntB[prefix][x]. 令cntA[prefix][!x]是以prefix为前缀, 并且sgA值不等于x的A的子串个数. 同理定义 cntB[prefix][!x].
首先, 我们要判断一下是否会打印NO. 其实只要K>必胜态的总数的话, 则就会打印NO, 否则绝不可能打印NO. 而所有必胜态的总数是多少呢? 就是
如果tot>=K的话, 就一定不是NO, 反之就是NO.
NO的问题解决了，我们来考虑怎么求第k小的必胜态. 假设第k小的必胜态是(sA, sB)
我们考察第一关键字字典序最小的情形即 sA=""的情况, 我们自然对有多少个sB使得 (sA, sB)为必胜态感兴趣.
首先A="ab"的SAM如下图所示（仅仅把trans画出来了，没有画slink， trans、slink这些基本概念可以学习【4】）
image
显然,因为 sgA("")=2（因为 sgA(1)=1, sgA(2)=0, 所以sgA("")=2, 即所谓的min exclude mex操作）, 所以有 cntB[""][!2] 个B中的子串使得 (sA, sB)为必胜态. 而B的SAM如下图所示（也没有画slink，只画了trans）
image
因为 sgB("c")=1, sgB("d") = sgB("cd") = 0，所以 cntB[""][!2]= 3
因为要求的K=5>3， 所以可以断定sA一定不会是空串. 排除掉刚刚sA=""情况下的三个必胜态, 我们只需要求剩余的必胜态中的字典序升序排第二（K=5-3=2, 切记, K已经变成2了哈~）的就是答案. 此时我们就需要判断sA的第一个字符sA[0]是什么?
和刚刚的思路一样, 我们也要计算出sA[0]='a'时（即以"a"为前缀）必胜态的个数. 根据乘法原理. 答案是
image
事实上, 我们具体计算一下就是（下面的计算式子中的sg位只出现了0、1、2 是因为就样例数据而言sg值只有0、1、2三种——因为A或者B的SAM的字符集都只有2个字符）
cntA["a"][0]*cntB[""][!0] + cntA["a"][1]*cntB[""][!1] + cntA["a"][2]*cntB[""][!2] = 1 * 2 + 1 * 3 + 0 * 3 = 5
因为5>K=2, 所以我们可以肯定sA[0]='a'了. 但是我们还想进一步确定一下sA四不四恰好就是 "a". 和上面计算sA=""情况一样, 因为 sgA("a") = 1, 所以答案就是 cntB[""][!1] =cntB[""][0]+cntB[""][2]=1+2=3(即"c"和"d","cd"这三个) 而K=2, 所以我们可以肯定sA就是"a"了. 下面开始确认sB是啥. 即找到已知sA="a" 的情况下, 第K=2小的sB使得(sA, sB)为必胜态（即1=sgA(sA)!=sgB(sB)）
计算的方式也是类似的. 我们先来看sB="" 时, 必胜态的个数, 显然就是1个（即 ("a", "")）. 所以我们的K要进一步减少1变成K=2-1=1（切记, 我们的K变成1了哈~）. 然后就要确定sB[0]. 所以我们要计算 cntB["a"][!1]、cntB["b"][!1]、 cntB["c"][!1]、…、cntB["z"][!1] 但是发现 cntB["a"][!1]、cntB["b"][!1] 都是0. 而 cntB["c"][!1] = 1(就是 "cd"), 所以可以确定sB的第一个字符是"c". 然后我们要看sB四不四恰好是"c", 显然不是——因为sgB("c") = 1=sgA("a"), 所以 ("a", "c")不是必胜态. 所以sB一定会有第二个字符. 所以我们要确定sB的第二个字符是什么. 注意到 cntB["ca"][!1]=cntB["cb"][!1]=cntB["cc"][!1]=0，cntB["cd"][!1]=1, 所以可以确定sB的第二个字符是d, 同时 (sA="a", sB="cd")是必胜态. 注意, 此时K减掉1之后就是0. 说明我们已经求出了第k小的必胜态为 ("a", "cd") 所以样例数据应该输出 ("a", "cd").
回顾上面的分析过程, 我们不难总结出解决本题的步骤
1. 首先判断是否是NO 2. 逐个字符地确定sA 3. 逐个字符地确定sB
总体步骤如上, 但是算法实现起来还是细节帝. 要仔细~
鉴于确定每个字符的时候我们大量依赖cntA（cntB），所以我们需要解决的最后的一个问题是
如何高效维护
cntA[prefix][x]与cntB[prefix][x]?
首先, 在使用SAM解决问题的时候, 一定要注意, 如果涉及的属性对于在同一个等价类中的所有子串是相等的话, 则就可以考虑使用SAM维护这一属性, 否则就一定不能使用SAM维护这一属性. 使用SAM来维护属性有什么好处? 好处在于SAM有优秀的DAG结构（【3】）以及slink树结构（【2】）, 有助于我们线性时间进行维护.
我们看看 cntA[prefix][x]是不是对于一个等价类中的所有子串都是相等的呢? 答案是肯定的， 因为prefix就决定了该子串从SAM的哪个顶点出发. 所以可以将cntA[prefix][x]视作是SAM的顶点的属性. 也就是说我们可以将cntA作为SAM的顶点的属性维护起来. 即本题的SAM节点上需要维护的属性不止有sg值, 还有cntA[x] 这种东西. 而因为字符集不超过26个英文字母, 所以根据sg值的mex类型的定义, x的取值范围（也就是sg值）不会超过26种， 所以每个顶点开一个长度为26的数组cnt作为属性就好了. 我们需要维护SAM节点的这个属性. 说到维护, 那自然要类似于【3】那样充分利用SAM站在trans角度上看是一张DAG这一性质来维护. 这也很简单. 父节点的cnt[x]=所有DAG后继节点的cnt[x]. 那么叶子节点（即SAM的终止状态）的cnt[x]是什么呢? 如果叶子节点的sg值等于x的话, 则叶子节点的cnt[x]=1, 否则等于0. 整个维护的复杂度显然是 O(26*N)， 可以接受的.
最后要注意, 本题可能爆int（前辈的必胜策略还真是多~ 所以和前辈打交道还是小心为上呢!）
本题分析完毕, 开始切代码~
//#include "stdafx.h" #pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <string.h> //#define LOCAL typedef long long ll; const int maxn = 1e5+5, SZ = 26; int na, nb; ll k; char a[maxn], b[maxn], sa[maxn], sb[maxn]; struct SamNode { int trans[SZ],slink, shortest, longest; int sg, leaf; // leaf =-1表示尚不知道该节点是否是叶子,0表示不是叶子, 1表示是叶子, cnt[i]是以该节点为前缀的sg值等于i的子串个数, rcnt[i]是以该节点为前缀的sg值不等于i的子串个数 ll cnt[SZ],rcnt[SZ]; bool ok; // true 表示此节点已经构建完毕cnt、rcnt了 }sama[maxn<<1], samb[maxn<<1]; int newnode(int shortest, int longest, int *trans, int slink, SamNode *sam, int &n) { sam[n].shortest = shortest; sam[n].longest = longest; sam[n].slink = slink; sam[n].sg = -1; sam[n].leaf = -1; trans?memcpy(sam[n].trans, trans, SZ*sizeof(int)):memset(sam[n].trans, -1, SZ*sizeof(int)); return n++; } int insert(char ch, int u, SamNode *sam, int &n) { int c = ch - 'a'; int z = newnode(-1, sam[u].longest+1, 0, -1, sam, n); int v = u; while(~v && !~sam[v].trans[c]) { sam[v].trans[c] = z; v = sam[v].slink; } if (!~v) { sam[z].shortest = 1; sam[z].slink = 0; return z; } int x = sam[v].trans[c]; if (sam[v].longest+1==sam[x].longest) { sam[z].shortest = sam[x].longest+1; sam[z].slink = x; return z; } int y = newnode(-1, sam[v].longest+1, sam[x].trans, sam[x].slink, sam, n); sam[x].shortest = sam[z].shortest = sam[y].longest+1; sam[x].slink = sam[z].slink = y; while(~v && sam[v].trans[c] == x) { sam[v].trans[c] = y; v = sam[v].slink; } sam[y].shortest = sam[sam[y].slink].longest+1; return z; } bool ck(SamNode &o) // 检查一个sam节点是不是叶子, true表示是叶子 { if (~o.leaf) { return o.leaf; } int outdeg = 0; for (int i = 0;i<SZ;i++) { if (~o.trans[i]) { return o.leaf = false; } } return o.leaf = true; } void sg(int cur, SamNode *sam) { if (~sam[cur].sg) { return; } if (ck(sam[cur])) { sam[cur].sg = 0; // 叶子是必败态, 所以sg值为0 return; } bool h[SZ] = {}; for (int i = 0, to;i<SZ; i++) { to = sam[cur].trans[i]; if (~to) { sg(to,sam); h[sam[to].sg] = true; } } int ans = 0; while(h[ans]) { ++ans; } sam[cur].sg = ans; } void cnt(int cur, SamNode *sam) { if (sam[cur].ok) { return; } if (ck(sam[cur])) { ll sum = 0; for (int i = 0; i<SZ; i++) { sam[cur].cnt[i] = i == sam[cur].sg; // 叶子即sam的终止状态,一定是原串的后缀, 则不可能还有什么子串以叶子为前缀了(除了叶子自身), 所以叶子的cnt[i]只有i恰好等于叶子的sg值的时候才是1, 否则是0 sum += sam[cur].cnt[i]; } for (int i = 0;i<SZ; i++) { sam[cur].rcnt[i] = sum - sam[cur].cnt[i]; } sam[cur].ok = true; return; } for (int i = 0, to;i<SZ; i++) { to = sam[cur].trans[i]; if (~to) { cnt(to,sam); for (int i = 0;i<SZ; i++) { sam[cur].cnt[i] += sam[to].cnt[i]; } } } ++sam[cur].cnt[sam[cur].sg]; // 自己的别落下. ll sum = 0; for (int i = 0;i<SZ; i++) { sum += sam[cur].cnt[i]; } for (int i = 0;i<SZ; i++) { sam[cur].rcnt[i] = sum - sam[cur].cnt[i]; } sam[cur].ok = true; } ll kk(int cur) // 计算以sama[cur]为前缀的必胜态的个数 { ll ans = 0; for (int i = 0;i<SZ; i++) { ans += sama[cur].cnt[i] * samb[0].rcnt[i]; } return ans; } bool solve() { int sg, cur = 0, i, pos = 0, pre; ll tot = 0, pretot; bool flag = true; for (i = 0;i<SZ; i++) // 检查所有必胜策略种数 { tot += sama[0].cnt[i] * samb[0].rcnt[i]; if (tot > k) // 如果计算完成tot的话,会连ll都爆掉,所以必须一旦超出k就break. { flag = false; break; } } if (flag) // 如果所有必胜策略种数<k的话, 则无解, 否则必有解 { puts("NO"); return false; } tot = 0; sg = sama[0].sg; // "" 在sama中的sg值 tot = samb[0].rcnt[sg]; // 所有 sa="" 情形下的必胜态种数 if (tot < k) // 说明sa不能是"" { k-=tot; while(1) // 确定sa { tot = 0; pretot = 0; pre = cur; for (i = 0; i<SZ; i++) // 确定sa[pos], 即确定前缀 { pretot = tot; cur = sama[pre].trans[i]; // 转移到某个前缀cur去 if (!~cur) { continue; } tot += kk(cur); if (tot>=k) { k-=pretot; sa[pos++] = 'a'+i; break; } } sg = sama[cur].sg; // 看看四不四恰好是这个前缀 if (samb[0].rcnt[sg]>=k) { break; // 说明恰好是这个前缀 } k-=samb[0].rcnt[sg]; // 说明sa不能仅仅是这个前缀, 后面还有字符 } } pos = 0; // 开始确定sb cur = 0; // 从samb 的起点开始出发 if (samb[0].sg ^ sg) // 说明sb=""也是必胜态 { if (k==1) // 说明答案就是 "" { return true; } --k; // 排除掉 sb=""的情况 } while(1) { tot = 0; pretot = 0; pre = cur; for (i = 0;i<SZ; i++) { pretot = tot; cur = samb[pre].trans[i]; if (!~cur) { continue; } tot += samb[cur].rcnt[sg]; if (tot >= k) { k-=pretot; sb[pos++] = 'a'+i; break; } } if (samb[cur].sg ^ sg) // 看看四不四恰好是这个前缀 { if (k==1) { break; } --k; } } return true; } int main() { #ifdef LOCAL freopen("d:\data.in", "r", stdin); freopen("d:\my.out", "w", stdout); #endif scanf("%lld%s%s", &k, a+1,b+1); int u = newnode(0, 0, 0, -1,sama, na); int i = 1; while(a[i]) { u = insert(a[i], u, sama, na); ++i; } u = newnode(0,0,0,-1, samb, nb); i = 1; while(b[i]) { u = insert(b[i], u, samb, nb); ++i; } for (int i = 0;i<na; i++) // 构建自动机sama上每个节点的sg值 { sg(i,sama); } for (int i = 0;i<nb; i++) { sg(i, samb); } for (int i = 0; i<na; i++) // 构建自动机sama上每个节点的cnt数组 { cnt(i, sama); } for (int i = 0; i<nb; i++) { cnt(i, samb); } if(solve()) { puts(sa); puts(sb); } return 0; }
ac情况
Accepted
通过本题我们知道——所谓的难题, 其实就是一些基本的简单题巧妙的组合在一起的.
参考
【1】《史上全网最清晰后缀自动机学习(二)后缀自动机的线性时间构造算法》
【2】《史上全网最清晰后缀自动机学习（三）后缀自动机里的树结构》
【3】《史上全网最清晰后缀自动机学习（四）后缀自动机里的DAG结构》
【4】《史上全网最清晰后缀自动机学习 (一) 基本概念入门》
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常
