史上全网最清晰后缀自动机学习（六）后缀自动机杂题

ACM算法日常

缘起

后缀自动机系列最后一发——后缀自动机和博弈的小综合~ 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情况