首页 > 代码库 > [AC自动机]题目合计
[AC自动机]题目合计
我只是想记一下最近写的题目而已喵~
题解什么的才懒得写呢~
[poj 1625]Censored!
这题注意一个地方,就是输入数据中可能有 ASCII 大于 128 的情况,也就是说用 char 读入时,这个字符的值为负数,真是 RE 了好久……
可以像我一样 map 党,你也可以把每个 s[i] 都加上 128
1 #include <cstdio> 2 #include <cstring> 3 #include <map> 4 #define max(x, y) ((x)>(y) ? (x):(y)) 5 const int digit=100000000; 6 const int sizeOfLen=64; 7 const int sizeOfMemory=1024; 8 const int sizeOfType=64; 9 10 struct bigint 11 { 12 int len; 13 int a[20]; 14 inline bigint():len(1) {memset(a, 0, sizeof(a));} 15 inline bigint & operator = (int x) {a[0]=x; return *this;} 16 inline bigint & operator += (bigint x) 17 { 18 len=max(len, x.len); 19 for (int i=0;i<len;i++) 20 { 21 a[i]+=x.a[i]; 22 a[i+1]+=a[i]/digit; 23 a[i]%=digit; 24 } 25 for ( ;a[len];len++) a[len+1]=a[len]/digit, a[len]%=digit; 26 return *this; 27 } 28 inline void print() 29 { 30 printf("%d", a[len-1]); 31 for (int i=len-2;i>=0;i--) printf("%08d", a[i]); 32 putchar(‘\n‘); 33 } 34 }; 35 36 int N, M, P; 37 char str[sizeOfLen]; 38 bigint f[sizeOfLen][sizeOfMemory]; 39 std::map<char, int> ord; 40 inline void dynamicProgram(); 41 42 namespace trieDfa 43 { 44 struct node 45 { 46 int order; 47 bool end; 48 node * fail; 49 node * ch[sizeOfType]; 50 }; 51 node memory[sizeOfMemory]; int port; 52 node * dfa=memory; 53 inline node * newnode() 54 { 55 node * ret=memory+port; 56 ret->order=port++; 57 ret->end=0; 58 ret->fail=NULL; 59 memset(ret->ch, 0, sizeof(ret->ch)); 60 return ret; 61 } 62 inline void clear() {port=0; dfa=newnode();} 63 64 inline void insert(char * s) 65 { 66 int len=strlen(s); 67 node * t=dfa; 68 for (int i=0;i<len;i++) 69 { 70 if (!t->ch[ord[str[i]]]) t->ch[ord[str[i]]]=newnode(); 71 t=t->ch[ord[str[i]]]; 72 } 73 t->end=1; 74 } 75 inline void buildDfa() 76 { 77 static node * queue[sizeOfMemory]; 78 int l=0, r=0; 79 80 dfa->fail=dfa; 81 for (int i=0;i<N;i++) 82 if (!dfa->ch[i]) dfa->ch[i]=dfa; 83 else dfa->ch[i]->fail=dfa, queue[r++]=dfa->ch[i]; 84 85 for ( ;l<r; ) 86 { 87 node * u=queue[l++]; 88 u->end|=u->fail->end; 89 for (int i=0;i<N;i++) 90 if (u->ch[i]) 91 { 92 u->ch[i]->fail=u->fail->ch[i]; 93 queue[r++]=u->ch[i]; 94 } 95 else 96 u->ch[i]=u->fail->ch[i]; 97 } 98 } 99 }100 101 int main()102 {103 scanf("%d %d %d", &N, &M, &P);104 scanf("%s", str);105 for (int i=0;i<N;i++) ord[str[i]]=i;106 trieDfa::clear();107 for (int i=0;i<P;i++)108 {109 scanf("%s", str);110 trieDfa::insert(str);111 }112 113 dynamicProgram();114 115 return 0;116 }117 inline void dynamicProgram()118 {119 bigint ret;120 121 trieDfa::buildDfa();122 123 f[0][0]=1;124 for (int i=0;i<M;i++)125 for (int j=0;j<trieDfa::port;j++)126 for (int k=0;k<N;k++) if (!trieDfa::dfa[j].ch[k]->end)127 f[i+1][trieDfa::dfa[j].ch[k]->order]+=f[i][j];128 ret=0;129 for (int i=0;i<trieDfa::port;i++) if (!trieDfa::dfa[i].end)130 ret+=f[M][i];131 ret.print();132 }
[hdu 2896]病毒侵袭
这真是裸体,而且数据没有 poj 那道丧心病狂
1 #include <cstdio> 2 #include <cstring> 3 const int sizeOfVirus=512; 4 const int sizeOfText=10025; 5 const int sizeOfType=128; 6 const int sizeOfMemory=100025; 7 8 int N, M; 9 char str[sizeOfText]; 10 int virus[sizeOfMemory]; 11 bool vis[sizeOfVirus]; 12 13 namespace IOspace 14 { 15 inline int getint() 16 { 17 register int num=0; 18 register char ch; 19 do ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 20 do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 21 return num; 22 } 23 inline void putint(int num) 24 { 25 char stack[10]; 26 register int top=0; 27 for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 28 for ( ;top;top--) putchar(stack[top]); 29 } 30 } 31 32 namespace trieDfa 33 { 34 struct node 35 { 36 int order; 37 bool end; 38 node * fail, * last; 39 node * ch[sizeOfType]; 40 }; 41 node memory[sizeOfMemory]; int port; 42 node * dfa=memory; 43 inline node * newnode() 44 { 45 node * ret=memory+port; 46 ret->order=port++; 47 ret->end=false; 48 ret->fail=ret->last=NULL; 49 memset(ret->ch, 0, sizeof(ret->ch)); 50 return ret; 51 } 52 inline void clear() {port=0; dfa=newnode();} 53 54 inline void insert(char * s, int k) 55 { 56 int len=strlen(s); 57 node * t=dfa; 58 for (int i=0;i<len;i++) 59 { 60 if (!t->ch[s[i]]) t->ch[s[i]]=newnode(); 61 t=t->ch[s[i]]; 62 } 63 t->end=true; 64 virus[t->order]=k; 65 } 66 inline void buildDfa() 67 { 68 static node * queue[sizeOfMemory]; 69 int l=0, r=0; 70 71 dfa->fail=dfa; 72 for (int i=0;i<sizeOfType;i++) 73 if (!dfa->ch[i]) dfa->ch[i]=dfa; 74 else dfa->ch[i]->fail=dfa, queue[r++]=dfa->ch[i]; 75 76 for ( ;l<r; ) 77 { 78 node * u=queue[l++]; 79 for (int i=0;i<sizeOfType;i++) 80 if (u->ch[i]) 81 { 82 u->ch[i]->fail=u->fail->ch[i]; 83 u->ch[i]->last=u->ch[i]->fail->end?u->ch[i]->fail:u->ch[i]->fail->last; 84 queue[r++]=u->ch[i]; 85 } 86 else 87 u->ch[i]=u->fail->ch[i]; 88 } 89 } 90 inline bool search(char * s) 91 { 92 bool flag=0; 93 int len=strlen(s); 94 95 node * t=dfa; 96 memset(vis, 0, sizeof(vis)); 97 for (int i=0;i<len;i++) 98 { 99 t=t->ch[s[i]];100 if (t->end) vis[virus[t->order]]=flag=true;101 for (node * j=t->last;j;j=j->last)102 vis[virus[j->order]]=flag=true;103 }104 105 return flag;106 }107 }108 109 int main()110 {111 int tot=0;112 113 N=IOspace::getint();114 trieDfa::clear();115 for (int i=1;i<=N;i++)116 {117 scanf("%s", str);118 trieDfa::insert(str, i);119 }120 trieDfa::buildDfa();121 122 M=IOspace::getint();123 for (int i=1;i<=M;i++)124 {125 scanf("%s", str);126 bool flag=trieDfa::search(str);127 tot+=flag;128 129 if (flag)130 {131 printf("web %d:", i);132 for (int i=1;i<=N;i++) if (vis[i])133 putchar(‘ ‘), IOspace::putint(i);134 putchar(‘\n‘);135 }136 }137 printf("total: %d\n", tot);138 139 return 0;140 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。