題意:有一個(gè)長(zhǎng)為n(n<= 25) 的字符串,它至少由k個(gè)magic word 組成,現(xiàn)在給出m個(gè)magic word,求出這個(gè)字符串組成的可能種數(shù)。
構(gòu)造AC自動(dòng)機(jī)進(jìn)行搜索,dp【i】【j】【k】表示字符串長(zhǎng)度為i,匹配字典樹(shù)上的第j個(gè)節(jié)點(diǎn),并且已經(jīng)匹配上k個(gè)magic word時(shí)的總數(shù)。
則轉(zhuǎn)移方程為 (dp【i+1】【j的兒子】【k ?| ?j的兒子的狀態(tài)】 += dp【i】【j】【k】) % mod;
需要注意的是,因?yàn)閱卧~可以重復(fù)使用,所以單詞結(jié)尾的fail 指向root 指向的各節(jié)點(diǎn)
?
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一類的 #define MAX 100005 #define mod 20090717 #define INF 0x7FFFFFFF #define REP(i,s,t) for(int i=(s);i<=(t);++i) #define LL long long #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) #define L(x) x << 1 #define R(x) x << 1 | 1 # define eps 1e-5 //#pragma comment(linker, "/STACK:36777216") ///傳說(shuō)中的外掛 using namespace std; struct Trie { int next[26] ; int fail ; int buff ; void init() { memset(next,0,sizeof(next)) ; fail = -1 ; buff = 0 ; } } a[111]; int cnt,n,m,K; int q[111] , dp[30][111][1 << 10]; char keyword[22]; void insert(char *s,int pos) { int p = 0 ; for(int i = 0 ; s[i] ; i ++) { int t = s[i] - 'a' ; if(a[p].next[t] == 0) { a[cnt].init(); a[p].next[t] = cnt ++; } p = a[p].next[t] ; } a[p].buff = 1 << pos; } void ac_bfs() { int i,head = 0,tail = 0; q[tail ++] = 0; while(head < tail) { int front = q[head ++]; for(i = 0; i < 26 ; i ++) { if(a[front].next[i] == 0) { if(front != 0) a[front].next[i] = a[a[front].fail].next[i]; } else { int p = a[front].fail ; while(p != -1) { if(a[p].next[i] != 0) { a[a[front].next[i]].fail = a[p].next[i] ; a[a[front].next[i]].buff |= a[a[p].next[i]].buff;//狀態(tài)合并,因?yàn)槿绻鹒ail指向的節(jié)點(diǎn)也是某個(gè)magic word的結(jié)尾,那么相當(dāng)于一次找到兩個(gè)magic word break ; } p = a[p].fail ; } if(p == -1) a[a[front].next[i]].fail = 0 ; q[tail ++] = a[front].next[i] ; } } } } int calone(int x) { int cal = 0; while(x) { if(x & 1) cal ++; x = x >> 1; } return cal; } void solve() { dp[0][0][0] = 1; int total = 1 << m; for(int i=0; i<n; i++) { for(int j=0; j<cnt; j++) { for(int k=0; k<total; k++) { if(dp[i][j][k] == 0) continue; for(int l=0; l<26; l++) { int buff = a[a[j].next[l]].buff; dp[i+1][a[j].next[l]][k | buff] = (dp[i+1][a[j].next[l]][k | buff] + dp[i][j][k]) % mod; } } } } int ans = 0; for(int j=0; j<cnt; j++) { for(int k=0; k<total; k++) { if(calone(k) < K) continue; ans = (ans + dp[n][j][k] ) % mod; } } printf("%d\n",ans); } int main() { while(scanf("%d%d%d",&n,&m,&K)) { if(n == 0 && m == 0 && K == 0) break; a[0].init(); cnt = 1; for(int i=0; i<m; i++) { scanf("%s",keyword); insert(keyword,i); } ac_bfs(); for(int i=0; i<=n; i++) { for(int j=0; j<cnt; j++) { for(int l=0; l<(1<<m); l++) { dp[i][j][l] = 0; } } } solve(); } return 0; }
?
現(xiàn)在缺少dp的思路和靈感.......照著別人的思路敲的.....有些地方依舊有待解決
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
