HDU 6208 The Dominator of Strings ——（青岛网络赛，AC自动机）

　　最长的才可能成为答案，那么除了最长的以外全部insert到自动机里，再拿最长的去match，如果match完以后cnt全被清空了，那么这个最长串就是答案。事实上方便起见这个最长串一起丢进去也无妨，而且更好写（时间也没有慢特别多）。

　　另外需要注意的一点是init()里头的memset只需要清空之前用过的节点而不是所有节点，这是经常被卡的一点。

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <queue>

 #include <vector>

 using namespace std;

 const int MAX_N =  + ;

 const int MAX_Tot =  + ;

 struct Aho

 {

     struct state

     {

         int nxt[];

         int fail,cnt;

     }stateTable[MAX_Tot];

     int size;

     queue<int> que;

     void init()

     {

         while(que.size()) que.pop();

         for(int i=;i<size;i++)

         {

             memset(stateTable[i].nxt,,sizeof(stateTable[i].nxt));

             stateTable[i].fail = stateTable[i].cnt = ;

         }

         size = ;

     }

     void insert(char *s)

     {

         int n = strlen(s);

         int now = ;

         for(int i=;i<n;i++)

         {

             char c = s[i];

             if(!stateTable[now].nxt[c-'a'])

                 stateTable[now].nxt[c-'a'] = size++;

             now = stateTable[now].nxt[c-'a'];

         }

         stateTable[now].cnt++;

     }

     void build()

     {

         stateTable[].fail = -;

         que.push();

         while(que.size())

         {

             int u = que.front();que.pop();

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

             {

                 if(stateTable[u].nxt[i])

                 {

                     if(u == ) stateTable[stateTable[u].nxt[i]].fail = ;

                     else

                     {

                         int v = stateTable[u].fail;

                         while(v != -)

                         {

                             if(stateTable[v].nxt[i])

                             {

                                 stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];

                                 break;

                             }

                             v = stateTable[v].fail;

                         }

                         if(v == -) stateTable[stateTable[u].nxt[i]].fail = ;

                     }

                     que.push(stateTable[u].nxt[i]);

                 }

             }

         }

     }

     //bool mark[MAX_Tot];

     void Get(int u)

     {

         while(u)

         {

             if(stateTable[u].cnt == -) break;

             stateTable[u].cnt = -;

             u = stateTable[u].fail;

         }

     }

     int match(char *s)

     {

         //memset(mark, 0, sizeof mark);

         int n = strlen(s);

         int res = , now = ;

         for(int i=;i<n;i++)

         {

             char c = s[i];

             if(stateTable[now].nxt[c-'a']) now = stateTable[now].nxt[c-'a'];

             else

             {

                 int p = stateTable[now].fail;

                 while(p != - && stateTable[p].nxt[c-'a'] == ) p = stateTable[p].fail;

                 if(p == -) now = ;

                 else now = stateTable[p].nxt[c-'a'];

             }

             Get(now);

         }

         for(int i=;i<size;i++) if(stateTable[i].cnt > ) return ;

         return ;

     }

 }aho;

 int T,n;

 char s[MAX_N], t[MAX_N];

 int main()

 {

     int T;scanf("%d",&T);

     while(T--)

     {

         vector<char> v;

         aho.init();

         scanf("%d",&n);

         int maxn = ;

         for(int i=;i<=n;i++)

         {

             scanf("%s",s);

             //aho.insert(s);

             int sz = strlen(s);

             for(int j=;j<sz;j++) v.push_back(s[j]);

             v.push_back('#');

             if(sz > maxn)

             {

                 maxn = sz;

                 strcpy(t, s);

             }

         }

         int tot = ;

         for(int i=;i<v.size();i++)

         {

             if(v[i] == '#')

             {

                 s[tot++] = ;

                 tot = ;

                 if(strcmp(s, t)) aho.insert(s);

             }

             else s[tot++] = v[i];

         }

         aho.build();

         int ans = aho.match(t);

         if(ans) puts(t);

         else puts("No");

     }

 }

巴特西

HDU 6208 The Dominator of Strings ——（青岛网络赛，AC自动机）

最新文章

热门文章