又是一个Trie图上找递推关系的题~只不过这次是单字符串做一个Trie图（这样的话用扩展kmp也可以8
把样例研究一下再结合Trie图基本就能确定出等式关系了，设dp[i]为
现在在Trie图上的节点i，还需要走多少步（期望意义下）才能凑出给定的字符串
容易知道当走到尽头的时候dp[n]=0;其他的项地推关系可以表示为dp[u]=1+\sum i/n*dp[v] ,其中v是u走向的下一个节点。
以样例n=2,s=”ABA”为例，Tried图和方程组如下
解这个方程组可得dp[0]=5,就是我们要的结果了。
具体代码实现的时候，直接对每个结点都把转移记录下来，然后用高斯消元解方程即可。注意应该把n乘到等式左边，然后用整数的高斯消元，不然会有误差wa。
继续阅读“[AC自动机][Trie图][期望DP][高斯消元] Generator UVALive 3490”
题目链接： Password Suspects
这题让我回想起了某现场赛被某大佬支配的恐惧
感觉是dp，而且这个子串的数据量一看就是状压，然后在推转移方程的时候死活推不出来一个不交叉的。可耻的搜了题解，看到大佬们的标题：AC自动机+DP
我就
~~其实是常见的一种操作只是我太久没做过字符串的题目了~~
在思考递推方程的时候就一直在纠结前缀与后缀重合的这种情况怎么表示状态，然后忽然意识到ac自动机（更确切的说是Trie图）就是可以唯一的确定一个匹配状态的数据结构！这种题一般都是给定一些字串，然后给出一些约束条件，比如要求
https://cn.vjudge.net/problem/HDU-3695
跟2222几乎一样，求文本中出现了多少个模式串，但是数据量变大了，5e6的长度。这时候用原来的写法已经会tle了，看到别人说用打标记的方式记录trie上一个节点有没有走过，一开始是不理解的，为什么这么做是正确的？后来想了想，AC自动机的算法确定了一个起点之后，沿着fail回溯的路径便已经确定（神奇），所以这条路上被走过的单词尾，再走的时候就会重复，而我们可以简单的把走过的节点计数标志变为-1，而在之后的过程中再遇到就可以不用管这个节点及其之后所有的节点了。注意这个是在while一开始就得判断。
WA的话，是从带括号的那个原串解压过后忘了在最后加’\0’。。。emmmm以后试验这种一定要从大到小试验数据。还有就是模板一定要用自己熟悉的。。原来以为这题问题在于kuangbin的板子不够快后来发现是没标记。。第二个是一开始没意识到q可以不止1位。。
继续阅读“[AC自动机][字符串][模板][优化] HDU3695 Computer Virus on Planet Pandora”
