hdu3695 AC自动机优化

题目链接：http://icpc.njust.edu.cn/Problem/Hdu/3695/

不加last指针的AC自动机会T，原因是他费了很多功夫在跳转上，而last指针是直接直到跳转的终止位置，直接跳转到终止位置上，所以只有一次跳转。未优化的fail指针最坏的情况下复杂度是O(|S|*|T|)，其中|S|是模式串长度的均值，|T|是文本串的长度。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 const int INF = 0x3f3f3f3f;

 const LL mod = 1e9+;

 typedef pair<int,int> pll;

 const int N = 1e6+;

 int tot = ;

 char str[N*], tmp[N*];

 int trie[N*][], cnt[N*], fair[N*];

 void init(){

     for(int i = ; i < tot; i++){

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

             trie[i][j] = ;

     }

     tot = ;

 }

 void Insert(){

     int rt = , len = strlen(str);

     for(int i = ; i < len; i++){

         int id = str[i] - 'A';

         if(!trie[rt][id]) {

             cnt[tot] = ;

             fair[tot] = ;

             trie[rt][id] = tot++;

         }

         rt = trie[rt][id];

     }

     cnt[rt]++;

 }

 void Build_tree(){

     queue<int> q;

     q.push();

     int p;

     while(!q.empty()){

         int tmp = q.front();

         q.pop();

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

             if(trie[tmp][j]){

                 if(tmp == )

                     fair[trie[tmp][j]] = ;

                 else {

                     p = fair[tmp];

                     while(p){

                         if(trie[p][j]){

                             fair[trie[tmp][j]] = trie[p][j];

                             break;

                         }

                         else p = fair[p];

                     }

                     if(!p) fair[trie[tmp][j]] = ;

                 }

                 q.push(trie[tmp][j]);

             }

         }

     }

 }

 int Find(int len){

     int ret = , rt = ;

     for(int i = ; i < len; i++){

         int id = str[i] - 'A';

         while(rt !=   && !trie[rt][id]) rt = fair[rt];;

         if(trie[rt][id]) rt = trie[rt][id];

         int p = rt;

         while(p != ){

             if(cnt[p] >= ){

                 ret += cnt[p];

                 cnt[p] = -;

             }

             else break;

             p = fair[p];

         }

     }

     rt = ;

     for(int i = len - ; i >= ; i--){

         int id = str[i] - 'A';

         while(rt !=   && !trie[rt][id]) rt = fair[rt];

         if(trie[rt][id]) rt = trie[rt][id];

         int p = rt;

         while(p != ){

             if(cnt[p] >= ){

                 ret += cnt[p];

                 cnt[p] = -;

             }

             else break;

             p = fair[p];

         }

     }

     return ret;

 }

 int main(){

     int t;

     scanf("%d", &t);

     while(t--){

         int n;

         init();

         scanf("%d", &n);

         while(n--){

             scanf("%s", str);

             Insert();

         }

         Build_tree();

         scanf("%s", tmp);

         int len = strlen(tmp);

         int ccc = ;

         for(int i = ; i < len; i++){

             if(tmp[i] != '['){

                 str[ccc++] = tmp[i];

             }

             else {

                 int _c = ;

                 i++;

                 while(isdigit(tmp[i]))

                     _c = _c * + (int)(tmp[i]-''), i++;

                 while(_c--)

                     str[ccc++] = tmp[i];

                 i++;

             }

         }

         printf("%d\n", Find(ccc));

     }

     return ;

 }

巴特西

hdu3695 AC自动机优化

最新文章

热门文章