AC自己主动机。
。。
当时感觉用字典树 标神也往自己主动机想来着。。手太生加上时间紧迫也没敲……回来一看题解什么AB同一时候建自己主动机。。。顿时愣了 什么叫同一时候建= =问了问財神说普通自己主动机。
。
。B串单建 立刻疯了……这不就是模板题么。。
。 B串建自己主动机 A串枚举查询 写完兴冲冲1T……立刻想法优化 建fail时压缩一下 查询时直接累计 不再循环找fail 171ms。。
。第二个自己主动机的题。。距上次蛮久了 这次一复习 感觉印象差点儿相同有了
代码(模板)例如以下:
#include#include #include #include #include using namespace std;typedef struct Node{ int ch[26],cnt,fail;}Node;Node tr[2600011];char a[100001][10002];int tp;int SetNode(){ memset(tr[tp].ch,-1,sizeof(tr[tp].ch)); tr[tp].cnt = 0; return tp++;}void Add(int site,char *str){ int i,k; for(i = 0; str[i]; ++i) { k = tr[site].ch[str[i] - 'a']; if(k == -1) tr[site].ch[str[i] - 'a'] = k = SetNode(); site = k; } tr[site].cnt++;}void Build_AC(int site){ queue q; q.push(site); int i,tmp; while(!q.empty()) { site = q.front(); q.pop(); for(i = 0; i < 26; ++i) { if(tr[site].ch[i] == -1) continue; if(!site) tr[tr[site].ch[i]].fail = 0; else { tmp = tr[site].fail; while(tmp && tr[tmp].ch[i] == -1) tmp = tr[tmp].fail; tr[tr[site].ch[i]].fail = (tr[tmp].ch[i] == -1)? tmp: tr[tmp].ch[i]; if(tr[tmp].ch[i] != -1) ///压缩计数器 tr[tr[site].ch[i]].cnt += tr[tr[tmp].ch[i]].cnt; } q.push(tr[site].ch[i]); } }}int Search(int site,char *str){ int i,k,ans = 0; for(i = 0; str[i]; ++i) { k = str[i] - 'a'; while(site && tr[site].ch[k] == -1) site = tr[site].fail; if(tr[site].ch[k] != -1) site = tr[site].ch[k]; ans += tr[site].cnt; } return ans;}int main(){ int t,na,nb,i; char str[100005]; scanf("%d",&t); while(t--) { scanf("%d %d",&na,&nb); tp = 0; SetNode(); for(i = 0; i < na; ++i) { scanf("%s",a[i]); } while(nb--) { scanf("%s",str); Add(0,str); } Build_AC(0); for(i = 0; i < na; ++i) { printf("%d\n",Search(0,a[i])); } } return 0;}