AC自动机主要解决多模式串匹配的问题,与dp有较多的结合。
AC自动机本质是在tire树上建立如同kmp一样的失配边。
所以建AC自动机首先要将模式串建成一颗tire树。
//tire树 const int maxn=100010;//最大结点总数 const int sigma=26; //字符集大小,即字符值必须为0~sigma-1 int ch[maxn][sigma]; //ch[i][j]表示结点i的沿字符j走一步所达到的结点 int val[maxn]; //附加信息 int sz; //结点总数 void init() //初始化函数 { sz=1; memset(ch[0],0,sizeof(ch[0])); } int idx(char c) //将字符编号 { return c-'a'; //内容根据题目调整 } //插入字符串s,附加信息为v。注意此处v必须非0。 void insert(char *s,int v) { int u=0,n=strlen(s); for(int i=0;i<n;i++) { int c=idx(s[i]); if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=v; //val[u]|=(1<<v); //状压时一般写成如上形式 }
建完tire树之后,就是AC自动机最重要的部分了,就是计算失配函数了。
//计算失配函数 int f[maxn]; //失配函数 int last[maxn]; //后缀链接 void getfail() //用bfs计算失配函数 { queue<int> q; f[0]=0; for(int c=0;c<sigma;c++) { int u=ch[0][c]; if(u) {f[u]=0;q.push(u);last[u]=0;} } while(!q.empty()) { int r=q.front();q.pop(); for(int c=0;c<sigma;c++) { int u=ch[r][c]; if(!u) { //ch[r][c]=ch[f[r]][c]; //将所有不存在的边补上,主要用于dp continue; } q.push(u); int v=f[r]; while(v && !ch[v][c]) v=f[v]; //当不存在的边补上后,此处可删去 f[u]=ch[v][c]; last[u]=val[f[u]]?f[u]:last[f[u]]; } } }
既然已经计算好了失配函数,那么就可以进行匹配了。
//在文本串T中找模板 int find(char *T) { int n=strlen(T); int j=0; for(int i=0;i<n;i++) { int c=idx(T[i]); while(j && !ch[j][c]) j=f[j]; //当失配边补全后,此处可删去 j=ch[j][c]; if(val[j]) process(j); else if(last[j]) process(last[j]); } } //递归进行操作 void process(int j) { if(j) { operate(); //具体操作视题目要求而定 process(last[j]); } }