昨天學習了一下AC自動機是什么東西，做了三道題
至于AC自動機的詳細解釋和資料可以通過搜索 Aho Corasick 找到很多相關論文和資料，我就不要班門弄斧了。
第一道hdu 2222,AC自動機的基本是用方法，直接應用在多模式匹配上。
第二道pku 2778 利用AC自動機減少狀態量，之后將狀態轉移做成矩陣，利用矩陣的二分乘法得到log級別的復雜度。
第三道pku 3691 使用同樣是利用AC自動機減少狀態量，由于狀態數太大不可能實現的dp，變成可能。
下面是后兩個題的代碼。
pku2778
??1?const?int?MOD?=?100000;
??2?
??3?struct?L
??4?{
??5???char?c;
??6???int?stat;
??7???bool?isend;
??8???L*?next[4],?*fail;
??9???L?()?{?isend?=?0,memset(next,?0,?sizeof(next)),?fail?=?NULL;}
?10?}pool[100];
?11?
?12?int?top;
?13?L?*?newL()
?14?{
?15???L?*?t?=?&pool[top];
?16???t->stat?=?top++;
?17???return?t;
?18?}
?19?
?20?int?c2i(char?t)
?21?{
?22???if?(t?==?'A')?{?return?0;?}
?23???if?(t?==?'C')?{?return?1;?}
?24???if?(t?==?'G')?{?return?2;?}
?25???if?(t?==?'T')?{?return?3;?}
?26???return?-1;
?27?}
?28?
?29?class?ACAutomata
?30?{
?31?public:
?32???L?*?root;
?33???void?init()
?34?????{
?35???????memset(pool,?0,?sizeof(pool));
?36???????top?=?0;
?37???????root?=?newL();
?38?????}
?39???ACAutomata(){?init();}
?40?
?41???void?ins(char?*s)
?42?????{
?43???????L?*?r?=?root;
?44???????for?(;*s;s++)?{
?45???????????int?t?=?c2i(*s);
?46???????????if?(r->?next[t]?==?NULL)?{
?47???????????????r->?next[t]?=?newL();
?48???????????}
?49???????????r?=?r->?next[t];
?50???????????r->?c?=?*s;
?51???????}
?52???????r->isend?=?true;
?53?????}
?54?
?55???void?pr()
?56?????{
?57???????int?i,?j;
?58???????queue<L*>?que;
?59???????que.push(root);
?60???????while?(!que.empty())?{
?61???????????int?sz?=?que.size();
?62???????????while?(sz--)?{
?63???????????????L*?r?=?que.front();que.pop();
?64???????????????if?(r?==?NULL)?{
?65???????????????????putchar('*');
?66???????????????????continue;
?67???????????????}
?68???????????????printf("[%d,?%d",?r->stat,?r->fail->stat);
?69???????????????if?(r->isend)?{
?70???????????????????printf("?#]?");
?71???????????????}else?{
?72???????????????????printf("?]?");
?73???????????????}
?74???????????????for?(i?=?0;i?<?4;i++)?{
?75???????????????????if?(r->next[i])?{
?76???????????????????????que.push(r->next[i]);
?77???????????????????}
?78???????????????}
?79???????????????que.push(NULL);
?80???????????}
?81???????????putchar(10);
?82???????}
?83?????}
?84?
?85???void?finish()
?86?????{
?87???????int?i;
?88???????queue<L*>?que;
?89???????root->fail?=?root;
?90???????for?(i?=?0;i?<?4;i++)?{
?91???????????if?(root->?next[i])?{
?92???????????????que.push(root->?next[i]);
?93???????????????root->?next[i]->?fail?=?root;
?94???????????}
?95???????}
?96???????while?(!que.empty())?{
?97???????????L?*r?=?que.front();que.pop();
?98???????????for?(i?=?0;i?<?4;i++)?{
?99???????????????if?(r->next[i])?{
100???????????????????L?*u?=?r->?next[i];?que.push(u);
101???????????????????L?*v?=?r->?fail;
102???????????????????while?(v?!=?root?&&?v->?next[i]?==?NULL)?{?v?=?v->?fail;?}
103???????????????????if?(v->?next[i])?{
104???????????????????????u->?fail?=?v->?next[i];
105???????????????????}else?{
106???????????????????????u->?fail?=?root;
107???????????????????}
108???????????????????u->isend?|=?u->fail->isend;
109???????????????}
110???????????}
111???????}
112?????}
113?}AC;
114?
115?int?m,?n,?dim;
116?char?s[51];
117?
118?struct?Matrix?{
119?????LL?a[100][100];
120?????Matrix()?{?memset(a,?0,?sizeof(a));?}
121?????LL?*?operator?[](int?idx)?{
122?????????return?a[idx];
123?????}
124?????void?pr()
125???????{
126?????????int?i,?j;
127?????????for?(i?=?0;i?<?dim;i++)?{
128?????????????for?(j?=?0;j?<?dim;j++)?{
129?????????????????printf("%lld?",?a[i][j]);
130?????????????}
131?????????????putchar(10);
132?????????}
133?????????putchar(10);
134???????}
135?}fac,?r;
136?
137?void?makeMatrix()
138?{
139???int?i,j;
140???queue<L*>?que;
141???que.push(AC.root);
142???while?(!que.empty())?{
143???????int?sz?=?que.size();
144???????while?(sz--)?{
145???????????L*?r?=?que.front();que.pop();
146???????????int?u?=?r->stat;
147???????????int?cnt?=?0;
148???????????for?(i?=?0;i?<?4;i++)?{
149???????????????if?(r->next[i])?{
150???????????????????if?(!r->next[i]->isend)?{
151???????????????????????int?v?=?r->next[i]->stat;
152???????????????????????fac[v][u]?++;
153???????????????????????que.push(r->next[i]);
154???????????????????}
155???????????????}else?{
156???????????????????L?*?cur?=?r->fail;
157???????????????????while?(cur?!=?AC.root?&&?cur->next[i]?==?NULL)?{?cur?=?cur->fail;?}
158???????????????????if?(cur->next[i])?{
159???????????????????????cur?=?cur->next[i];
160???????????????????}
161???????????????????if?(!cur->isend)?{
162???????????????????????int?v?=?cur->stat;
163???????????????????????fac[v][u]?++;
164???????????????????}
165???????????????}
166???????????}
167???????}
168???}
169???dim?=?top;
170???for?(i?=?0;i?<?dim;i++)?{
171???????for?(j?=?0;j?<?dim;j++)?{
172???????????fac[i][j]?%=?MOD;
173???????}
174???}
175?}
176?
177?Matrix?mul(Matrix?a,?Matrix?b)
178?{
179???int?i,j,k;
180???Matrix?r;
181???for?(i?=?0;i?<?dim;i++)?{
182???????for?(j?=?0;j?<?dim;j++)?{
183???????????for?(k?=?0;k?<?dim;k++)?{
184???????????????r[i][j]?=?(r[i][j]?+?(a[i][k]?*?b[k][j])?%?MOD?)?%?MOD;
185???????????}
186???????}
187???}
188???return?r;
189?}
190?
191?Matrix?pow(const?Matrix?&a,?int?times)
192?{
193???if?(times?==?1)?{
194???????return?a;
195???}
196???Matrix?r?=?pow(a,?times?>>?1);
197???r?=?mul(r,?r);
198???if?(times?&?1)?{
199???????r?=?mul(r,?a);
200???}
201???return?r;
202?}
203?
204?int?main()
205?{
206???int?i,?j,?k;
207???scanf("%d?%d",?&m,?&n);
208???while?(m--)?{
209???????scanf("%s",?s);
210???????AC.ins(s);
211???}
212???AC.finish();
213???if?(Debug)?{
214???????AC.pr();
215???}
216???makeMatrix();
217???if?(Debug)?{
218???????fac.pr();
219???}
220???Matrix?r?=?pow(fac,?n);
221?
222???int?ans?=?0;
223???for?(i?=?0;i?<?dim;i++)?{
224???????ans?=?(ans?+?r[i][0])?%?MOD;
225???}
226???printf("%d\n",?ans);
227???return?0;
228?}
229?pku3691
??1?const?int?N?=?1024;
??2?struct?L?{
??3?????int?stat;
??4?????int?c,?isend;
??5?????L*?fail;
??6?????L*?next[4];
??7?????L()?{?stat?=?0,?c?=?0,?fail?=?NULL,?memset(next,?0,?sizeof(next));}
??8?}pool[N],?*root;
??9?const?int?inf?=?0x7f7f7f7f;
?10?int?top;
?11?int?dp[1024][1024];
?12?char?s[2048];
?13?int?n,?len;
?14?
?15?int?c2i(char?t)
?16?{
?17???if?(t?==?'A')?{?return?0;?}
?18???if?(t?==?'C')?{?return?1;?}
?19???if?(t?==?'G')?{?return?2;?}
?20???if?(t?==?'T')?{?return?3;?}
?21???return?-1;
?22?}
?23?
?24?void?init()
?25?{
?26???top?=?0;
?27???memset(pool,?0,?sizeof(pool));
?28???memset(dp,?0x7f,?sizeof(dp));
?29???dp[0][0]?=?0;
?30???root?=?&pool[top++];
?31?}
?32?
?33?void?ins(char?s[])
?34?{
?35???L*?r?=?root;
?36???for?(char?*?t?=?s;*t;t++)?{
?37???????int?idx?=?c2i(*t);
?38???????if?(r->next[idx]?==?NULL)?{
?39???????????r->next[idx]?=?&pool[top];
?40???????????r->next[idx]->stat?=?top++;
?41???????}
?42???????r?=?r->next[idx];
?43???}
?44???r->isend?=?true;
?45?}
?46?
?47?void?finish()
?48?{
?49???int?i;
?50???queue<L*>?que;
?51???root->fail?=?root;
?52???for?(i?=?0;i?<?4;i++)?{
?53???????if?(root->next[i])?{
?54???????????que.push(root->next[i]);
?55???????????root->next[i]->fail?=?root;
?56???????}
?57???}
?58???while?(!que.empty())?{
?59???????L*?r?=?que.front();que.pop();
?60???????for?(i?=?0;i?<?4;i++)?if?(r->next[i])?{
?61???????????L?*u?=?r->next[i];?que.push(r->next[i]);
?62???????????L?*v?=?r->fail;
?63???????????while?(v?!=?root?&&?v->next[i]?==?NULL)?{?v?=?v->fail;?}
?64???????????if?(v->next[i])?{?v?=?v->next[i];?}
?65???????????u->fail?=?v;
?66???????????u->isend?|=?u->fail->isend;
?67???????}
?68???}
?69?}
?70?
?71?void?pr(L?*root)
?72?{
?73???int?i,j,k;
?74???queue<L*>?que;
?75???que.push(root);
?76???while?(!que.empty())?{
?77???????int?sz?=?que.size();
?78???????while?(sz--)?{
?79???????????L*?r?=?que.front();que.pop();
?80???????????if?(r?==?NULL)?{
?81???????????????printf("*?");
?82???????????????continue;
?83???????????}
?84???????????printf("[%d,%d]?",?r->stat,?r->fail->stat);
?85???????????for?(i?=?0;i?<?4;i++)?{
?86???????????????if?(r->next[i])?{
?87???????????????????que.push(r->next[i]);
?88???????????????}
?89???????????}
?90???????????que.push(NULL);
?91???????}
?92???????putchar(10);
?93???}
?94???for?(i?=?0;i?<?top;i++)?{
?95???????printf("[%d,?%d]?",?pool[i].stat,?pool[i].fail->stat);
?96???}
?97???putchar(10);
?98?}
?99?
100?int?main()
101?{
102???L*?r;
103???int?i,j,k,?stat,?testid?=?1;
104???while(scanf("%d",?&n)?==?1?&&?n)?{
105???????init();
106???????for?(i?=?0;i?<?n;i++)?{
107???????????scanf("%s",?s);
108???????????ins(s);
109???????}
110???????finish();
111???????if?(Debug)?{
112???????????pr(root);
113???????}
114???????scanf("%s",?s?+?1);
115???????len?=?strlen(s?+?1);
116???????for?(i?=?1;i?<=?len;i++)?{
117???????????for?(j?=?0;j?<?top;j++)?{
118???????????????for?(k?=?0;k?<?4;k++)?{
119???????????????????if?(dp[i-1][j]?<?inf?&&?!pool[j].isend)?{
120???????????????????????int?cost?=?(k?!=?c2i(s[i]));
121???????????????????????if?(pool[j].next[k])?{
122???????????????????????????r?=?pool[j].next[k];
123???????????????????????}else?{
124???????????????????????????r?=?pool[j].fail;
125???????????????????????????while?(r?!=?root?&&?r->next[k]?==?NULL)?{
126???????????????????????????????r?=?r->fail;
127???????????????????????????}
128???????????????????????????if?(r->next[k])?{
129???????????????????????????????r?=?r->next[k];
130???????????????????????????}
131???????????????????????}
132???????????????????????if?(!r->isend)?{
133???????????????????????????stat?=?r->stat;
134???????????????????????????ckmin(dp[i][stat],?dp[i-1][j]?+?cost);
135???????????????????????}
136???????????????????}
137???????????????}
138???????????}
139???????}
140???????if?(Debug)?{
141???????????printf("info\n");
142???????????for?(i?=?0?;i?<=?len;i++)?{
143???????????????for?(j?=?0;j?<?top;j++)?{
144???????????????????printf("%12d",?dp[i][j]);
145???????????????}
146???????????????putchar(10);
147???????????}
148???????????putchar(10);
149???????}
150???????int?ans?=?inf;
151???????for?(i?=?0;i?<?top;i++)?{
152???????????ckmin(ans,?dp[len][i]);
153???????}
154???????if?(ans?==?inf)?{
155???????????ans?=?-1;
156???????}
157???????printf("Case?%d:?%d\n",?testid++,?ans);?
158???}
159?
160???return?0;
161?}
162?
163?