【题解】2019校内测试字符串-白红宇

【题解】2019校内测试字符串

阅读量：5276 次

发布时间：2019-06-14

本文共 1559 字，大约阅读时间需要 5 分钟。

请自觉忽视解密后的输入……

一道正常的题，一个奇怪的做法

首先看到这个题就要想到AC自动机

但一般的AC自动机只支持一次询问，否则会出现死循环

原因是在建立fail指针的代码中的这句话：

if (node[u].ch[i]) {    node[node[u].ch[i]].fail=node[node[u].fail].ch[i];    q.push(node[u].ch[i]);} else {    node[u].ch[i]=node[node[u].fail].ch[i];}

这句话意味着当当前节点没有某儿子时，儿子指针会指向失配节点的那个儿子

那么就有可能有这种情况：

所以我们要想一个办法来避免这种情况的发生

最简单的做法：

把多出来的儿子指针（图中蓝色指针）去掉

换句话说，还原建fail指针之前的自动机

于是就有了如下的代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #define int long longusing namespace std;const int N=2000010;struct note { int fail; int ch[26]; int str_end;};int ch_bak[N][26];struct AC { note node[N]; int siz; AC() { siz=1; } inline int id(char ch) { return ch-'a'; } inline void insert(char s[],int val) { int len=strlen(s); int u=0; for(int i=0;i

q; while(!q.empty()) { q.pop(); } for(int i=0;i<=siz;i++) { for(int j=0;j<=25;j++) { ch_bak[i][j]=node[i].ch[j]; } node[i].fail=0; } for(int i=0;i<26;i++) { if (node[0].ch[i]!=0) { node[node[0].ch[i]].fail=0; q.push(node[0].ch[i]); } } while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<26;i++) { if (node[u].ch[i]) { node[node[u].ch[i]].fail=node[node[u].fail].ch[i]; q.push(node[u].ch[i]); } else { node[u].ch[i]=node[node[u].fail].ch[i]; } } } } inline void back() { for(int i=0;i<=siz;i++) { for(int j=0;j<=25;j++) { node[i].ch[j]=ch_bak[i][j]; } } } inline int query(char s[]) { int len=strlen(s); int u=0,ans=0; for(int i=0;i

时间复杂度O(m∑|s|)，按理来说过不去，可出题人并没有卡，加之常数较小，就这么过了……

转载于:https://www.cnblogs.com/tt66ea-blog/p/11311522.html

你可能感兴趣的文章