那啥由于我讲的这玩意Suffix Automaton的定义和证明之类的东西太多了。。。。。。
不得以就讲的跟堆定义一样。。。。。
时间也非常紧。。。感觉40分钟读一遍定义都差不多了。。讲的太快也请大家见谅T_T。。。
其实ppt做到还是很详细的。。。如果讲的时候没有跟上可以慢慢看ppt。。。。
资料在我的skydrive网盘的OI文件夹的all.rar里
另外我现在对于我的选材感到非常的后悔。。本来我的题目应该是
“根号算法与分块思想”。。。。。。。
那啥由于我讲的这玩意Suffix Automaton的定义和证明之类的东西太多了。。。。。。
不得以就讲的跟堆定义一样。。。。。
时间也非常紧。。。感觉40分钟读一遍定义都差不多了。。讲的太快也请大家见谅T_T。。。
其实ppt做到还是很详细的。。。如果讲的时候没有跟上可以慢慢看ppt。。。。
资料在我的skydrive网盘的OI文件夹的all.rar里
另外我现在对于我的选材感到非常的后悔。。本来我的题目应该是
“根号算法与分块思想”。。。。。。。
Orz…..话说解释超时问题时我当场就笑了……
内啥，为什么我下不了SKYDRIVE上的文件呢
orz
spoj太慢了
没找到
去哪找？
回复turtle33333：我空间首页右上角有个网盘
还不错啊。。。
PPT放出来的话显然这个比分块好多了
怎么证明while (p && !p->go[w]) p->go[w]=np,p=p->par;和while (p && p->go[w]==q) p->go[w]=nq,p=p->par;这两步是线性的呢？
回复xudyh：可以使用均摊分析来证明。。。具体你可以自己想想
orz 不把ppt上显示不出的那个式子补上去吗？
回复yaosiqiu：似乎是mac上pptx到win下转换时崩掉的。。有时间补一下
回复WJBZBMR：求补完…
我想问个问题：串“acbbbab”的Parent树共10个节点，其中Root = 0，节点按生成顺序编号的话，这棵Parent树是：par[1] = 0;par[2] = 0;par[5] = 0;par[8] = 1;par[3] = 5;par[7] = 5;par[9] = 5;par[4] = 7;par[6] = 7;可以看到，节点1的唯一孩子是叶节点8，但是节点1所表示的状态的Right集合是{1, 6}，节点8的Right集合是{6}，那么节点1的Right集合就不是子节点的并集了，和PPT第26页中说的“状态的Right就是它Parent树中所有孩子Right集合的并集”不一样。请问能不能讲一下这是为什么？
ppt的18页，为什么Right（a） = Right(b) => ST(a) = ST(b) ? 可否证明一下？