《acm 竞赛题知识点总结》由会员分享，可在线阅读，更多相关《acm 竞赛题知识点总结（12页珍藏版）》请在金锄头文库上搜索。
1、滚动数组（转）版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明http:/ 题目中，因为DP题目是一个自下而上的扩展过程，我们常常用到是连续的 解，而每次用到的只是解集中的最后几个解，所以以滚动数组形式能大大减 少内存开支。用法：#include using namespace std;int d3;int main()(d0 = 1;d1 = 1;for( int i = 2; i 100; i+)di % 3 = d(i - 1) % 3 + d(i - 2 % 3;cout d99 % 3 endl; / Fibonacci. return 0;int i,j,d2100
2、;/比 d100100省多了for(i=1;i100;i+)for(j=0;j100;j+)di%2j=d(i-1)%2j+di%2j-1;/ DP 滚动数组举个简单的例子: int i,d100;d0=1;d1 = 1;for(i=2;i100;i+)di=di-1+di-2;printf(%d,d99);上面这个循环di只需要解集中的前2个解di-1和di-2;为了节约空间用滚动数组的方法 int d3;d0=1;d1 = 1;for(i=2;i100;i+)di%3=d(i-1)%3+d(i-2)%3;printf(%d,d99%3);注意上面的运算，我们只留了最近的3个解，数组好象在“
3、滚动 一样，所 以叫滚动数组对于二维数组也可以用这种方法 例如：int i,j,d100100;for(i=1;i100;i+)for(j=0;j100;j+)dij=di-1j+dij-1;上 的 dij忪便赖于 di-1j,dij-1;迥用滚动数组int i,j,d2100;for(i=1;i100;i+)for(j=0;jnextindex = = NULL) p-nextindex=new node();7 p=p-nextindex;8 i+ + ;10p-count+;在单词的最后一个节点count+1,代表一个单词11 在构造完这棵Tire之后，接下去的工作就是构造下失败指针。构
4、造失败指针的过程概括起来就 一句话：设这个节点上的字母为C,沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也 有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了 root 都没找到，那就把失败指针指向root。具体操作起来只需要：先把root加入队列(root的失败指针 指向自己或者NULL)，这以后我们每处理一个点，就把它的所有儿子加入队列，队列为空。1 void build_ac_automation(node *root)2 int i;3 root-fail = NULL;4 qhead + = root;5 while(head!=tail)6
5、node *temp=qtail+;7 node *p=NULL;8 for(i = 0;inexti! = NULL)10 if(temp= = root) temp-nexti-fail = root;11 else12 p=temp-fail;13 while(p! = NULL)14 if(p-nexti! = NULL)15 temp-nexti-fail = p-nexti;171816 break;p=p-fail;1920if(p= = NULL) temp-nexti-fail = root;2122 qhead +=temp-nexti;23 24 25 26 从代码观察下
6、构造失败指针的流程：对照图-2来看，首先root的fail指针指向NULL,然后 root入队，进入循环。第1次循环的时候，我们需要处理2个节点：root-nexth-a（节点h） 和root-nexts-a（节点s）。把这2个节点的失败指针指向root，并且先后进入队列，失败 指针的指向对应图-2中的（1），（2）两条虚线；第2次进入循环后，从队列中先弹出h，接下来p 指向h节点的fail指针指向的节点，也就是root；进入第13行的循环后，p=p-fail也就是 p=NULL，这时退出循环，并把节点e的fail指针指向root，对应图-2中的（3），然后节点e进 入队列；第3次循环时，弹出的第一个节点a的操作与上一步操作的节点e相同，把a的fail指 针指向root，对应图-2中的（4），并入队；第4次进入循环时，弹出节点h（图中左边那个），这时 操作略有不同。在程序运行到14行时，由于p-nexti! = NULL（root有h这个儿子节点，图中 右边那个），这样便把左边那个h节点的失败指针指向右边那个root的儿子节点h，对应图-2中 的（5），然后h入队。以此类推：在循环结束后，所有的失败指针就是图-2中的这种形式。最后，我们便可以在AC自动机上查找模式串中出现过哪些单词了。匹配过程分两种情况：(1)当 前字符匹配，表示从当前
