hdu 4117 AC自动机 + DP+线段树

此题着实蛋疼。。。。 写了个简单的dp 我居然交了20次代码后有个ac出现。。。。不知道此题数据是不是现场随机生成在跑的。。。

题意：给定n个字符串，每个串都有个权值，找出若干个字符串组成一个序列，前面一个字符串是后面一个字符串的子串，问我们能获得最大权值和？

首先dp方程应该好想吧 到dp[i] 到以第i个串结尾的最大权值和

首先把所有串一起加入trie建自动机， 那么fail指针指向的所有节点必然是前面有的子串。

所以这里在每个点val值就要变一下，即要改成对于每个串的id我能涵盖的trie上的节点编号是哪些 即match[id]=u;  u是当前trie的节点//这里debug好久啊啊啊啊啊啊啊！！！

然后 对于到第i个位置，我从trie的根节点开始往下扫，看能到达哪几个子串，然后加上即可

但是这样做的复杂度会相当的高

这里要用线段树优化

首先我们根据fail指针建边，然后dfs一次，对于每个节点访问多少次，看对于每个接受fail指针的节点有多少个指向他，那么就是一边dfs序

由于fail指针的走向呈线性变化

然后我们用线段树的段更新将这一段的节点都可以更新了。询问的时候对于当前点询问就可以了。

然后我们再找一遍最大dp值就好了。。。。