2019-10-21

hdu 4117 GRE Words AC自动机+Fail树+线段树+dfs+DP

缘起

学习ac自动机的一些高级话题~ hdu 4117 GRE Words

分析

就是现在给出n (n <= 20000)个单词, 每个单词由一些小写字母组成, 现在这些单词按照输入的顺序给定, 
每个单词还有一个权值, 当然可能出现某个单词出现了两次, 即两个串完全一样但是多次出现, 权值还可能不同, 
那么如果将这n个单词删掉一些之后, 剩下的单词满足按照原本输入的顺序排列, 上面一个是下面一个的子串, 
这种删除方法是合法的, 求在所有合法的删除方案中剩下的单词的权值和最大是多少, 输入的单词总长度不超过30W

【输入】
多样例. 第一行是样例数, 每个样例第一行是单词的数量n,然后是n行,
每行由一个单词+一个整数（[-1000,1000]）

【输出】
对每个样例输出最大的重要程度之和

【样例输入】
1
5
a 1
ab 2
abb 3
baba 5
abbab 8

【样例输出】
Case #1: 14

【限制】
15s 32MB

这是一道比较综（过）合（瘾）的题目~

其实此题要联合【1】来看就会发现, 其实和【1】十分十分的像. 其基本思想都是树状数组（或者说线段树）优化dp. 为什么这么说呢? 【1】中用树状数组优化lis的dp公式是

1 2	dp[i]=max{dp[j]+1}(1<=j< i,a[j]<= a[i]) 其中dp[i] 是以a[i]为结尾的LIS的长度. 我们在递推dp数组的时候

但是发现每次dp的时候, 要遍历所有的 a[j]<=a[i] && j<i ,时间复杂度太高. 所以就改变dp的对象为

dp[i]为原数组从小到大排序第i的元素为结尾的lis的最大长度. 
则 dp[i] = max{dp[j]+1}, 1<=j<i
即a[j]<=a[i]的限制被去掉了. 因为排名在i前面的一定比排名为i的小.
而去掉了这个限制的话, 就是典型的前缀性质(max)的维护. 而前缀性质的维护, 不论是部分和也好, 还是区间
极值也好, 不正是树状数组的拿手好戏吗? 所以才有了树状数组优化dp的手段登场.

注意, “从小到大’’ 这其实是一种偏序关系.

那本题是怎么回事呢, 本题的偏序关系就是一个串是另一个串的子串. 即如果a是b的子串的话, 则就说a<b.

注意, 【1】中dp之所以可以顺利进行, 是因为从小到大这种偏序关系通过简单的排序就能实现. 那么对于本题的偏序关系怎么实现呢? bingo! fail指针啊~ 【2】中fail指针不就是刻画了一个串是另一个串的子串这种关系吗?（确切讲是一个串是另一个串的子串）. 但是如果a的fail指针如果指向b的话, 则其实就是b是a的指子串（这和偏序关系正好相反）. 所以就不难理解为什么要利用fail指针反向建树. 即所谓的ac自动机的fail树（这棵fail树的根节点自然就是trie的根节点啦~ fail树你到【2】的第一幅图中将箭头反向就是了）然后这棵树其实就定义了本题中的偏序关系——父节点是子节点的子串.

然后我们来看看本题的dp公式（其实和LIS真的非常像）

1 2	用dp[i]表示最终剩下的串以第i个串结尾的的方案中权值和的最大值那么dp[i] = max(dp[j] + w[i]) 1 <= j < i, 其中第j个串是第i个串的子串.

【1】中为了使用树状数组优化LIS, 而将dp的舞台从原本的a[1,…,n]变到了排序之后的a[1,…,n]（因为排序之后的a满足偏序关系）类比的, 本题dp的舞台也要从原先的 s[1,..,n]（n个串, 按照读入的顺序排列）变动到fail树上. 因为一旦到了fail树上, 对于每个串i（对应ac自动机上的一个节点）, 它的dp值dp[i]的求解就转变为如下的问题

父亲结点中已经求解出dp值的这些dp值的最大值是多少? 这个最大值加上w[i]（即当前串的权重）就是当前串i
的dp值dp[i].
ps: 其实和【1】也非常相似——【1】中求解dp[i]（即原数组中从小到大排名第i的元素的dp值）的时候, 排在它
前面的数组元素（即比它小的元素）的dp值未必已经求解出来了.因为比它小的这些元素可能在原数组中排在i之后.

你看到没有? 所谓的难题, 不过是简单题组合在一起罢了.

说了这么多, 写代码了. 注意, 【3】中对ac自动机的实现采用了链表, 遂觉得不妥（速度慢）~ 所以才考虑将其转换为数组版本的. 而且处于构建fail树的需要, 使用数组比使用链表版本方便的多

最后借鉴【5】，我们再将本题的思路整体说一遍。

首先, 初心是如下朴素的dp

用dp[i]表示从第1个单词，到第i个单词，所有以第i个单词结尾的情况中最大权值和是多少。

dp[i]=max(dp[v]+weight[i])，要求第v个单词是第i个单词的子串且v<i。
但是上面的朴素dp是显然会被T掉的. 优化点是原先的n个串预处理出ac自动机+fail反向建树.

fail反向建树能保证fail树的父节点是子节点的后缀. 而一个串的子串不就是该串的某个前缀的后缀吗? 所以我们在使用这n个串预处理出ac自动机并且预处理出fail树之后, 再预处理出该fail树的dfs序, 确切讲是得到fail树中每个节点A的in（初次发现）和out（离开时间）, 则时间区间[in,out]就是以此节点A为根的子树的欧拉环游的游历时间.

注意, ac自动机上每个节点都有fail指针.所以fail树节点的集合其实和ac自动机的节点集合是相同的, 只是组织的形式不同而已, ac自动机组织在一起是通过trie的next指针, 而fail树组织这些节点显然就是靠fail指针

然后我们根据游历fail树的时间戳建立线段树. 那么线段树上每个节点都代表一段游历的时间戳（确切讲就是上面说的[in,out]）. 线段树上每个节点维护该节点代表的时间戳范围内所有的fail树节点的dp值的最大值. 也就是, 我们将每个fail树上的节点都赋予了dp值,而不仅仅是能代表某个串的fail树节点(即串末尾的字符)才赋予dp值（注意, 其实从代码实现角度来讲, 我们只会对线段树上每个节点赋予dp域, 但是因为fail树节点本质上就是线段树的叶子, 所以下面也会说fail树节点的dp值, 并不区分）. 而fail树上的节点其实就是线段树的叶子节点. 而fail树上每个节点的dp值的意义是什么呢（线段树的非叶子节点的dp值好解释——就是子树中每个节点的dp域的最大值, 关键就是解释清楚叶子节点的dp含义）? 我们按照原先顺序考察每个串, 假设考察到了第i个串, 则此时fail树上每个节点(即线段树的叶子节点)的dp值的含义是已经考察完了的串中以当前fail树节点表示的前缀（trie不就是前缀树吗?) 为合法结尾的最大权重和. 怎么说?

例如我们有串 ab、a、abcd、abc, 权重分别是10,9,20,30，然后现在已经考察了ab,a 即我们已经考察到了abcd这个串. 则’c’这个字符对应ac自动机上一个节点（当然, 也是fail树上的一个节点）, 而’c’代表的前缀是abc, 则’c’对应fail树节点（线段树的叶子节点）的dp值等于10, 因为ab、abc构成的序列权重是10, 而a、abc构成的序列的权重是9. 9<10, 所以取10. 虽然 abc这个前缀并不是任何串. 但是它也是有dp值的.

即整个算法的情况应该是下面这个样子.

现在对于当前考察的串（例如上面例子中的abcd，或者上图中的best）, 只需要遍历它的所有前缀（例如上面例子是abcd, 它的所有前缀是a、ab、abc、abcd(注意, 包括自己, 因为本题可能有重复单词！),或者上图中的best, 它的前缀是b、be、bes、best），然后每个前缀其实都是fail树上的节点（亦即线段树中的叶子节点）询问该线段树叶子节点的dp值. 对这些dp值取max得到的结果再加上当前串的权重值就得到了当前串最后那个字符（例如上图中的’t’）代表的fail树节点对应到线段树叶子节点的dp值.

为什么?

这是本算法的关键, 你看看上图， dp[‘t’] = max{dp[‘b’], dp[‘e’], dp[‘s’], dp[‘t’]}+”best”的权重. 因为从best的某个前缀出发按照fail树走就是合法的以best为结尾的序列. 例如”bes”是best的前缀. bes按照fail树走, 得到的序列拼上（当然, 去掉bes）best就是符合题意的（偏序）序列. 而这种出发, 既可以从best出发, 也可以从bes出发, 也可以从be出发, 也可以从b出发. 所以才要取max

因为注意, 这里取max并不能是由线段树快速得到, 只能一个一个for遍历所有前缀得到. 因为这些前缀代表的线段树叶子节点，而这些叶子节点并不在一个连续的时间戳内~（注意, 不要搞错了——一个串的前缀节点们如果按照ac自动机dfs序的话,如果没有分叉的话, 还可能在一个连续的时间戳内, 但是按照fail树的dfs序意义下, 一般不会在一个连续时间戳内）所以就无法使用线段树进行优化. 只能线段树单点询问——而且每次询问都是询问叶子节点（因为fail树节点就是线段树的叶子）。那么得到串的最后那个字符对应的线段树叶子节点的dp值之后还需要做什么吗? 你得知道, 这个节点虽然是线段树的叶子节点, 但是可能是fail树的非叶子节点P, 即它对应的fail树节点P可能是某棵fail子树的根. 而P的fail树意义下的节点Q们对应到线段树的叶子节点Q1们的dp值（上面说过了, Q和Q1并不区分）就要发生相应变化了——因为根据fail树的意义, P都是Q们的后缀. 所以Q们的dp值也要取max变化. 那P能波及影响的Q1范围恰好就是区间[P.in, P.out], 即我们要区间（延迟）更新线段树，来（延迟）更新这些被影响的线段树叶子节点（对应就是这些Q们）的dp值.

所以本题涉及线段树的操作是单点询问（这里的单点其实是叶子），区间（延迟）更新

本题细节还是比较多的. 能1a本题着实不容易~

而且本题线段树的引入根本不是为了快速求max（如上所见, max还是要老老实实的遍历得到）. 其实dp完全可以在fail树上进行dp就行了, 即上面说的

1 2	dp['t'] = max{dp['b'], dp['e'], dp['s'], dp['t']}+w["best"] （甲）这没问题~

但是为什么要引入线段树呢? 根据我们上面的论述, 其实线段树并没有起到快速维护求解max的作用（因为’b’、’e’、’s’、’t’在fail树欧拉环游意义下时间戳并不连续, 因此无法快速维护）. 原因在于线段树平衡！如果直接在fail树上dp的话，根据上述公式甲，计算dp[‘t’]没有任何问题.dp的含义也不需要变化. 会出现问题的是一个fail树节点的dp变了, 如何去快速更新该fail树节点的所有子节点的dp值. 如果ac自动机的深度足够大的话, 则这种更新的速度将会很慢。会T掉的. 所以线段树的作用是使得fail树的深度变得平均起来. 从而更新的更加迅速.

//#include "stdafx.h"
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 20005, SIZE = 26, maxm = 300005;
int w[maxn],n,cnt, timestamp; // cnt是ac自动机节点个数
vector<string> words; // 这里不能轻易使用数组,防止MLE(毕竟本题的空间卡的比较紧)
string tmp;
vector<int> g[maxm]; // (反向)fail树
typedef vector<int>::iterator vit;
struct AcNode
{
	int fail, next[SIZE],in,out; // fail指针, next指针, in和out分别是欧拉环游遍历fail树时本节点的时间戳, in 是首次发现当前节点,out是离开时间戳
	char c; // 仅用于debug
	AcNode():fail(0),in(0),out(0){memset(next,0,sizeof(next));}
}acm[maxm]; // 因为总共的文本不超过30w个字符, 所以trie的节点最多30w个节点

struct SegmentTreeNode
{
	int begin,end;
	int mmax; // 此线段树节点维护的(区间)最大值(你想想,【1】不也就是这样吗? 只是【1】是树状数组而已),对于叶子, mmax就是文章中说的dp值
	bool lazy; // 是否延迟加载
}segmentTree[maxm<<2]; // 本题ac自动机和线段树的根节点都是从1索引开始的,0索引皆不用

void insert() // 将string tmp插入trie构建字典树
{
	int p = 1,len = tmp.length();
	for (int i = 0;i<len; i++)
	{
		if (!acm[p].next[tmp[i]-'a'])
		{
			acm[p].next[tmp[i]-'a'] = ++cnt; // 最后trie有cnt个节点, 即acm[1,...,cnt], 其中1是根节点
			acm[acm[p].next[tmp[i]-'a']].c = tmp[i]; // 仅仅用于debug
		}
		p = acm[p].next[tmp[i]-'a'];
	}
}

void makefail() // bfs制作fail指针
{
	queue<int> q;
	for (int i = 0;i<SIZE;i++)
	{
		if (acm[1].next[i])
		{
			acm[acm[1].next[i]].fail = 1;
			q.push(acm[1].next[i]);
		}
	}
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		for (int i = 0;i<SIZE;i++)
		{
			if (acm[front].next[i])
			{
				int f = acm[front].fail;
				while(f!=1 && !acm[f].next[i])
				{
					f = acm[f].fail;
				}
				acm[acm[front].next[i]].fail = acm[f].next[i]?acm[f].next[i]:1;
				q.push(acm[front].next[i]);
			}
		}
	}
}

void dfs(int cur) // 欧拉环游fail树,当前环游到了acm[cur]节点, 记录时间戳. 要是你弄懂了【4】, 这里就会很容易弄懂
{
	acm[cur].in = ++timestamp;
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		dfs(*x);
	}
	acm[cur].out = timestamp; // 则[acm[cur].in,acm[cur].out] 这个闭区间就是游历以acm[cur]为根的fail子树花费的时间. 即从acm[cur].in时刻进入这棵子树, 在acm[cur].out时刻离开这棵子树
}

void failtree() // 反向fail指针建立fail树
{
	for (int i =1;i<=cnt;i++)
	{
		g[i].clear();
	}
	for (int i =1;i<=cnt;i++)
	{
		if (acm[i].fail)
		{
			g[acm[i].fail].push_back(i); // 有fail指针 从acm[i]这个节点指向 acm[i].fail这个节点, 则反向fail就是 acm[i].fail->i 这条树边（弧）
		}
	}
	timestamp = 0; // 时间戳
	dfs(1); // 开始欧拉环游fail树, 建立时间戳in、out
}

void build(int begin,int end,int cur) // 构建（点）线段树
{
	segmentTree[cur].begin = begin, segmentTree[cur].end = end;
	segmentTree[cur].mmax = 0;
	segmentTree[cur].lazy = 0;
	if (begin==end)
	{
		segmentTree[cur].lazy = true; // 其实无所谓, 线段树叶子节点必回头
		return;
	}
	int mid = segmentTree[cur].begin+segmentTree[cur].end>>1;
	build(begin,mid,cur<<1);
	build(mid+1,end,cur<<1|1);
}

void pushdown(int cur) // 下推延迟标记
{
	if (segmentTree[cur].lazy)
	{
		segmentTree[cur<<1].mmax = max(segmentTree[cur<<1].mmax, segmentTree[cur].mmax);
		segmentTree[cur<<1|1].mmax = max(segmentTree[cur<<1|1].mmax, segmentTree[cur].mmax);
		segmentTree[cur<<1].lazy = segmentTree[cur<<1|1].lazy = true;
		segmentTree[cur].lazy = false;
	}
}

int query(int cur,int i) // 单点查询, 查询的是线段树维护的区间[1,timestamp]中的i时间戳这一点的值
{
	if (segmentTree[cur].begin==segmentTree[cur].end) // 到底了
	{
		return segmentTree[cur].mmax;
	}
	pushdown(cur); // 下推延迟标记(因为查询必须要下推)
	int mid = segmentTree[cur].begin+segmentTree[cur].end>>1;
	if (i<=mid)
	{
		return query(cur<<1,i);
	}
	else
	{
		return query(cur<<1|1, i);
	}
}

void updata(int begin, int end, int cur, int t) // 将线段树维护的区间[1,timestamp]的子区间[begin,end]的值改成t,这一举动会造成很多线段树节点的最大值的改变,确切讲是和[begin,end]有交集的区间的mmax都要和t做max
{
	if (segmentTree[cur].begin == segmentTree[cur].end || segmentTree[cur].begin==begin && segmentTree[cur].end == end && t>=segmentTree[cur].mmax) // 注意, 延迟更新只能是t更大才行,t小的话, 是不能延迟更新的, 见文章附录分析
	{
		segmentTree[cur].mmax = max(segmentTree[cur].mmax, t); // 延迟更新线段树(但是不同的是, 这里的线段树仅仅是没有继续向下更新, 本身已经更新了),注意, 因为能进入这段代码不仅仅是t>=segmentTree[cur].mmax,也可能是到了叶子,所以这里要取max,而不能直接等于t
		segmentTree[cur].lazy = true;
		return; 
	}
	pushdown(cur);
	int mid = segmentTree[cur].begin+segmentTree[cur].end>>1;
	if (end<=mid)
	{
		updata(begin,end,cur<<1,t);
	}
	else if (begin>mid)
	{
		updata(begin, end, cur<<1|1, t);
	}
	else
	{
		updata(begin, mid, cur<<1, t);
		updata(mid+1,end, cur<<1|1, t);
	}
	segmentTree[cur].mmax = max(segmentTree[cur].mmax, t); // 这里立即更新比较简单, 因为可以方便的立即更新
}

int solve()
{
	int len = words.size(), ans = 0;
	for (int i = 0, cur, t;i<len; i++) // 按照原先的顺序考察每个单词 words[i]
	{
		cur = 1,t = 0;
		for (int j =0, sz = words[i].length();j<sz; j++)
		{
			cur = acm[cur].next[words[i][j]-'a']; // 注意, 因为ac自动机就是由words构成的,所以cur一定不为0,这里不需要做判断
			t = max(t, query(1,acm[cur].in)); // 单点询问线段树的叶子——即环游初次发现时间戳为acm[cur].in的fail节点
		}
		updata(acm[cur].in, acm[cur].out, 1, t+w[i]); // 区间更新线段树的 [acm[cur].in, acm[cur].out] 这个区间
		ans = max(ans, t+w[i]); // 更新ans
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	ios::sync_with_stdio(0); // 防止cin慢
	int kase;
	scanf("%d", &kase);
	for (int i = 1;i<=kase;i++)
	{
		memset(acm, 0, sizeof(acm));
		cnt = 1; // ac自动机的root是数组的1号节点
		cin>>n;
		words.clear();
		for (int i = 0;i<n;i++)
		{
			cin>>tmp>>w[i];
			words.push_back(tmp);
			insert();
		}
		makefail(); // bfs制作fail指针
		failtree(); // 反向fail建立fail树
		build(1,timestamp,1); // 建立[1,timestamp]上的线段树, 维护并回答极值就是在[1,timestamp]区间上进行的
		printf("Case #%d: %d\n", i, solve());
	}
	return 0;
}

很遗憾~ 此题被MLE掉了~ 本题空间卡的太紧了~ 所以耍个无赖, 将maxm由30w改成25w, 凸(艹皿艹 ), 竟然a了!

即ac代码如下（C++提交才行, G++提交会蜜汁wa）

//#include "stdafx.h"
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 20005, SIZE = 26, maxm = 250005;
int w[maxn],n,cnt, timestamp;
vector<string> words;
string tmp;
vector<int> g[maxm];
typedef vector<int>::iterator vit;
struct AcNode
{
	int fail, next[SIZE],in,out;
}acm[maxm]; 

struct SegmentTreeNode
{
	int begin,end;
	int mmax;
	bool lazy;
}segmentTree[maxm<<2];

void insert()
{
	int p = 1,len = tmp.length();
	for (int i = 0;i<len; i++)
	{
		if (!acm[p].next[tmp[i]-'a'])
		{
			acm[p].next[tmp[i]-'a'] = ++cnt;
		}
		p = acm[p].next[tmp[i]-'a'];
	}
}

void makefail()
{
	queue<int> q;
	for (int i = 0;i<SIZE;i++)
	{
		if (acm[1].next[i])
		{
			acm[acm[1].next[i]].fail = 1;
			q.push(acm[1].next[i]);
		}
	}
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		for (int i = 0;i<SIZE;i++)
		{
			if (acm[front].next[i])
			{
				int f = acm[front].fail;
				while(f!=1 && !acm[f].next[i])
				{
					f = acm[f].fail;
				}
				acm[acm[front].next[i]].fail = acm[f].next[i]?acm[f].next[i]:1;
				q.push(acm[front].next[i]);
			}
		}
	}
}

void dfs(int cur)
{
	acm[cur].in = ++timestamp;
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		dfs(*x);
	}
	acm[cur].out = timestamp;
}

void failtree()
{
	for (int i =1;i<=cnt;i++)
	{
		g[i].clear();
	}
	for (int i =1;i<=cnt;i++)
	{
		if (acm[i].fail)
		{
			g[acm[i].fail].push_back(i);
		}
	}
	timestamp = 0; 
	dfs(1); 
}

void build(int begin,int end,int cur) 
{
	segmentTree[cur].begin = begin, segmentTree[cur].end = end;
	segmentTree[cur].mmax = 0;
	segmentTree[cur].lazy = 0;
	if (begin==end)
	{
		segmentTree[cur].lazy = true; 
		return;
	}
	int mid = segmentTree[cur].begin+segmentTree[cur].end>>1;
	build(begin,mid,cur<<1);
	build(mid+1,end,cur<<1|1);
}

void pushdown(int cur)
{
	if (segmentTree[cur].lazy)
	{
		segmentTree[cur<<1].mmax = max(segmentTree[cur<<1].mmax, segmentTree[cur].mmax);
		segmentTree[cur<<1|1].mmax = max(segmentTree[cur<<1|1].mmax, segmentTree[cur].mmax);
		segmentTree[cur<<1].lazy = segmentTree[cur<<1|1].lazy = true;
		segmentTree[cur].lazy = false;
	}
}

int query(int cur,int i) 
{
	if (segmentTree[cur].begin==segmentTree[cur].end)
	{
		return segmentTree[cur].mmax;
	}
	pushdown(cur);
	int mid = segmentTree[cur].begin+segmentTree[cur].end>>1;
	if (i<=mid)
	{
		return query(cur<<1,i);
	}
	else
	{
		return query(cur<<1|1, i);
	}
}

void updata(int begin, int end, int cur, int t) 
{
	if (segmentTree[cur].begin == segmentTree[cur].end || segmentTree[cur].begin==begin && segmentTree[cur].end == end && t>=segmentTree[cur].mmax) 
	{
		segmentTree[cur].mmax = max(segmentTree[cur].mmax, t); 
		segmentTree[cur].lazy = true;
		return; 
	}
	pushdown(cur);
	int mid = segmentTree[cur].begin+segmentTree[cur].end>>1;
	if (end<=mid)
	{
		updata(begin,end,cur<<1,t);
	}
	else if (begin>mid)
	{
		updata(begin, end, cur<<1|1, t);
	}
	else
	{
		updata(begin, mid, cur<<1, t);
		updata(mid+1,end, cur<<1|1, t);
	}
	segmentTree[cur].mmax = max(segmentTree[cur].mmax, t);
}

int solve()
{
	int len = words.size(), ans = 0;
	for (int i = 0, cur, t;i<len; i++)
	{
		cur = 1,t = 0;
		for (int j =0, sz = words[i].length();j<sz; j++)
		{
			cur = acm[cur].next[words[i][j]-'a'];
			t = max(t, query(1,acm[cur].in));
		}
		updata(acm[cur].in, acm[cur].out, 1, t+w[i]);
		ans = max(ans, t+w[i]); 
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	ios::sync_with_stdio(0); 
	int kase;
	scanf("%d", &kase);
	for (int i = 1;i<=kase;i++)
	{
		for (int i = 1;i<=cnt; i++)
		{
			for (int j = 0;j<SIZE; j++)
			{
				acm[i].next[j] = 0;
			}
		}
		cnt = 1;
		cin>>n;
		words.clear();
		for (int i = 0;i<n;i++)
		{
			cin>>tmp>>w[i];
			words.push_back(tmp);
			insert();
		}
		makefail();
		failtree();
		build(1,timestamp,1);
		printf("Case #%d: %d\n", i, solve());
	}
	return 0;
}

ac情况（跑的还算快~）

Status	Accepted
Time	2714ms
Memory	30088kB
Length	4038
Lang	C++
Submitted	2019-10-24 10:54:21
Shared
RemoteRunId	31072035

参考

【1】https://yfsyfs.github.io/2019/10/21/%E6%B4%9B%E8%B0%B7%E3%80%90p1020%E3%80%91%E5%AF%BC%E5%BC%B9%E6%8B%A6%E6%88%AA-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E4%BC%98%E5%8C%96%E6%B1%82LIS/

【2】https://yfsyfs.github.io/2019/10/11/ac%E8%87%AA%E5%8A%A8%E6%9C%BA%E5%AD%A6%E4%B9%A0/

【3】https://yfsyfs.github.io/2019/10/13/hdu-2222-Keywords-Search-ac%E8%87%AA%E5%8A%A8%E6%9C%BA%E6%9D%BF%E9%A2%98/

【4】https://yfsyfs.github.io/2019/07/15/LCA/

【5】https://blog.csdn.net/weixin_33734785/article/details/85706318

附录

为什么代码中 updata 方法只能在叶子节点或者刚好符合区间长度而且t>=当前节点的mmax才能延迟更新? 因为看下图

如果去掉不论啥t都有让更新的话, 则变成下图

而这显然是不对的!因为线段树根节点的mmax显然要恒保持>=子节点的mmax（不管是否延迟更新）. 具体讲因为 [5,6]节点的mmax变成0, 而且lazy还变成了true, 则表明[5,6]节点的整棵树的最大值都是0~ 但是[6,6]节点的mmax显然是1! 所以[5,6]上的信息mmax=0且lazy=true错误的! 所以必须要加这个限制——不是所有的t都能延迟更新的~ 正因为比较麻烦, 所以一些网上大神的代码对updata函数根本不进行延迟更新.