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

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

---

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

首先看到这个题就要想到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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#define int long long
using 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<len;i++) {
            int c=id(s[i]);
            if (!node[u].ch[c]) {
                node[u].ch[c]=siz++;
            }
            u=node[u].ch[c];
        }
        node[u].str_end+=val;
    }
    inline void fail() {
        queue<int> 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<len;i++) {
            u=node[u].ch[id(s[i])];
            for(int t=u;t;t=node[t].fail) {
                ans+=node[t].str_end;
            }
        }
        back();
        return ans;
    }
};

int n;
char s[N];
AC t;

signed main() {
    scanf("%d",&n);
    int mask=0;
    for(int i=1;i<=n;i++) {
        int opx;
        scanf("%d %s",&opx,s);
        opx^=mask;
        if (opx==3) {
            t.fail();
            int qwq=t.query(s);
            mask^=abs(qwq);
            printf("%d
",qwq);
        } else {
            if (opx==1) {
                t.insert(s,1);
            } else {
                t.insert(s,-1);
            }
        }
    }
    return 0;
}

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