Keywords Search HDU2222 AC自动机模板题

ac自动机说起来很复杂，其实和kmp是一样的思路，都是寻找相同前后缀，减少跳的次数。只要理解了kmp是怎么求next数组的，ac自动机bfs甚至比knp还好写。

这里大致说一下kmp求next数组的方法吧，假设现在要求第c个字符的next值(假设这个c很大，这样画图出来比较清晰方便理解)，因为遍历过程中我们已经知道了第c-1个字符的next为x(假设比c小很多)，即next[c-1] = x。那就代表我们知道了a[1]—a[x]这一段和a[c-1-x]—a[c-1]这一段是相等的对吧。

那么现在有两种情况

一。a[x+1] 和 a[c]相等，那么显然变成了a[1]—a[x+1] 这一段和a[c-1-x]—a[c]这一段相等，即c位置的相同前后缀长度比c-1多了1，就是next[c-1]+1；

即原来是：

1——————————x == c-1-x ————————————————c-1 ① 由于a[x+1] == a[c]，变成了

1——————————x+1 == c-1-x——————————————————c

二。如果不相等，那么我们在1——x这一段下功夫，假设next[x] = y，即1——y == x-y——x这两段相等，注意根据①式，x-y——x == c-1-y——c-1，画个图就很清楚了，所以如果a[y+1] == a[c]，那么相同前后缀长度就是y+1了。

即因为

1——————————x == c-1-x————————————————c-1　　

1——y == x-y———x == c-1-x——c-1-x+y == c-1-y————c-1 　　由于a[y+1] == a[c]，变成了

1——y+1　　　　　　　　　　　　　== 　　　　　　　 c-1-y——————c

那如果a[y+1] 与a[c]还是不相等怎么办？其实细心的话应该发现这是一个递归过程了——只要再找next[y]，循环上面的过程就可以了，想明白这个过程再去看求next数组的代码就很容易理解了。

最后还是上这道题代码：

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <queue>

 #include <set>

 #include <stack>

 #include <math.h>

 #include <string>

 #include <algorithm>

 #define SIGMA_SIZE 26

 #define pii pair<int,int>

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) (x&-x)

 #define fode(i, a, b) for(int i=a; i>=b; i--)

 #define foe(i, a, b) for(int i=a; i<=b; i++)

 #define fod(i, a, b) for(int i=a; i>b; i--)

 #define fo(i, a, b) for(int i=a; i<b; i++)

 //#pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a, LL b) { return a>b ? a : b; }

 inline LL LMin(LL a, LL b) { return a>b ? b : a; }

 inline LL lgcd(LL a, LL b) { return b ==  ? a : lgcd(b, a%b); }

 inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; }  //a*b = gcd*lcm

 inline int Max(int a, int b) { return a>b ? a : b; }

 inline int Min(int a, int b) { return a>b ? b : a; }

 inline int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b); }

 inline int lcm(int a, int b) { return a / gcd(a, b)*b; }  //a*b = gcd*lcm

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL lmod = 1e9+;

 const int mod = ;

 const double eps = 1e-;

 const int inf = 0x3f3f3f3f;

 const int maxk = 1e5+;

 const int maxm = *;

 const int maxn = 5e5+;

 struct node {

     node *fail, *s[];

     int w;

     node() {}

     void init() {

         fail = NULL;

         fo(i, , ) s[i] = NULL;

         w = ;

     }

 }*head;

 int n, ans;

 char str[];

 queue<node*> q;

 node* getfail(node* p, int x)

 {

     if (p->s[x] != NULL) return p->s[x];

     else {

         if (p == head) return head;

         else return getfail(p->fail, x);

     }

 }

 void build()

 {

     node* root = head;

     node* tmp;

     int len = strlen(str);

     for ( int j = ; j < len; j++ )

     {

         int k = str[j]-'a';

         if (root->s[k] == NULL) {

             tmp = new node; tmp->init();

             tmp->fail = head;

             root->s[k] = tmp;

         }

         root = root->s[k];

         //标记单词结尾

         if (j == len-) root->w++;

     }

 }

 void build_ac()

 {

     node* r;

     while(!q.empty()) q.pop();

     q.push(head);

     while(!q.empty())

     {

         r = q.front(); q.pop();

         fo(j, , )

         {

             if (r->s[j] != NULL) {

                 q.push(r->s[j]);

                 if (r == head) r->s[j]->fail = head;

                 else r->s[j]->fail = getfail(r->fail, j);

             }

         }

     }

     return;

 }

 void solve()

 {

     int len = strlen(str);

     node *tmp, *r = head;

     fo(j, , len)

     {

         int k = str[j]-'a';

         //找到前缀

         while( r->s[k]==NULL && r != head ) r = r->fail;

         //自动机向下匹配

         //如果可以匹配，则进入下一节点，否则返回头节点

         r = (r->s[k]==NULL) ? head : r->s[k];

         tmp = r;

         //如果单词a出现，则他的前缀也全部出现过

         while(tmp != head) {

             ans += tmp->w;

             tmp->w = ;

             tmp = tmp->fail;

         }

     }

     return;

 }

 void init()

 {

     cin >> n; ans = ;

     head = new node, head->init();

     foe(i, , n)

         scanf("%s", str), build();

     build_ac();

     scanf("%s", str);

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("input.txt", "r", stdin);

     #endif

     int t; cin >> t;

     while(t--)

     {

         init();

         solve();

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

Keywords Search HDU2222 AC自动机模板题

最新文章

热门文章