AC自动机+dp.doc

Pku3691DNA repair:给定m个病毒DNA片段，在给一个DNA序列，求最小经过多少次改动可以消去病毒序列。无法则输出-1.Pku2778DNA，也是给你m个病毒DNA片段，求长度为N的没有病毒序列的种数结果mod100000。Pku1625，给定字母表E,在给你n个禁止出现子序列，求长度为M的序列有多少种，输出结果。高精度。PKU3691#includeusing namespace std;const int size = 1003;const int MAXINT = 130;int dpsizesize;char word24;char strsize;struct Node int end,fail,son4; void Init() end = 0; fail = -1; memset(son, -1, sizeof(son); nodesize;int node_Num = 0;int qsize,head,tail;int Index(char a) switch(a) case A:return 0; case G:return 1; case C:return 2; case T:return 3; void Insert(char *s) int p = 0; for(int i=0; si; i+) if (nodep.sonIndex(si) = -1) node_Num+; nodep.sonIndex(si) = node_Num; nodenode_Num.Init(); if (nodep.end) break;/*危险结点为其子结点不必继续 */ p = nodep.sonIndex(si); nodep.end+;void Build_Ac() int temp, p, i; head = tail = 0; qtail+ = 0; while (head tail) temp = qhead+; for (i = 0; i b|a=-1) a=b;int Done() int i, j, k, Min = MAXINT, tmp; memset(dp, -1, sizeof(dp); dp00 = 0; for (i = 0; stri; i+) for (j = 0; j = node_Num; j+) if (dpij != -1) for (k = 0; k 4; k+) tmp = j; while (tmp != -1) if (nodetmp.sonk != -1) tmp = nodetmp.sonk; break; tmp = nodetmp.fail; if (tmp = -1) tmp = 0; if (!nodetmp.end) toMin(dpi+1tmp, dpij+(Index(stri)!= k);/*1or0*/ for (j = 0; j dpij) Min = dpij; return (Min=MAXINT)?-1:Min;int main() int N, i, ans, Case=1; while (scanf(%d,&N) & N) node_Num = 0; node0.Init(); for (i = 0; i N; i+) scanf(%s,word); Insert(word); scanf(%s,str); Build_Ac(); ans = Done(); printf(Case %d: %dn,Case+, ans); return 0;PKU2778#includeusing namespace std;const int Mod = 100000;const int size = 120;_int64 gsizesize;struct Node int fail,son4,end; void Init() fail = -1; memset(son, -1, sizeof(son); end = 0; nodesize;int node_Num = 0;int qsize, head, tail;int Index(char a) switch (a) case A:return 0; case G:return 1; case C:return 2; case T:return 3; void Insert(char *s) int p=0; for (int i=0; si; i+) if (nodep.end) break; if (nodep.sonIndex(si) = -1) node_Num+; nodep.sonIndex(si) = node_Num; nodenode_Num.Init(); p = nodep.sonIndex(si); nodep.end+;void Build_Ac() head = tail = 0; int temp = 0, p = 0, i; qtail+ = 0; while (head tail) temp = qhead+; for (i = 0; i 4; i+) if (nodetemp.soni != -1) if (temp = 0) nodenodetemp.soni.fail = 0; else p = nodetemp.fail; while (p != -1) if (nodep.soni != -1) nodenodetemp.soni.fail = nodep.soni; if (nodenodep.soni.end) nodenodetemp.soni.end+; break; p = nodep.fail; if (p = -1) nodenodetemp.soni.fail = 0; qtail+ = nodetemp.soni; void MatrixMul(_int64 bsize, _int64 csize, int sz) int i, j, k; _int64 tempsizesize = 0; for (i = 0; i sz; i+) for (j = 0; j sz; j+) for (k = 0; k = Mod) tempij %= Mod; for (i = 0; i sz; i+) for (j = 0; j 0) if (n&1) MatrixMul(tot,a, sz); MatrixMul(a, a, sz); n = 1; int N = 2000000000;int M;char word14;_int64 totsizesize;int main() int i, j; while (scanf(%d%d, &M, &N) != EOF) node_Num = 0; node0.Init(); memset(g, 0, sizeof(g); for (i = 0; i M; i+) scanf(%s, word); Insert(word); Build_Ac(); node_Num+; for (i = 0; i node_Num; i+) if(!nodei.end) for (j = 0; j 4; j+) if (nodei.sonj != -1 & nodenodei.sonj.end=0) ginodei.sonj+; else if (nodei.sonj= -1) if (i=0) g00+; else int temp = i; while (nodetemp.sonj= -1) if (temp=0)break; temp = nodetemp.fail; if(nodetemp.sonj != -1 & nodenodetemp.sonj.end=0) ginodetemp.sonj+; else if (nodetemp.sonj= -1& temp=0) gi0+; mem