bzoj 4327 AC自动机

思路：将能跑到的状态标记一下，在bfs搜一下就好啦。

#include<bits/stdc++.h>

#define LL long long

#define ll long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define y1 skldjfskldjg

#define y2 skldfjsklejg

using namespace std;

const int N = 1e7 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

int n, m, len[], pos[];

char s[N], t[];

struct Ac {

    int ch[N][], f[N], d[N], tot, sz;

    Ac(int sz) {this->sz = sz;}

    void init() {tot = ;}

    int newNode() {

        tot++; f[tot] = ;

        memset(ch[tot], , sizeof(ch[tot]));

        return tot;

    }

    inline int idx(char c) {

        if(c == 'E') return ;

        if(c == 'S') return ;

        if(c == 'W') return ;

        if(c == 'N') return ;

    }

    void addStr(char *s, int ID) {

        int u = ;

        for(int i = ; s[i]; i++) {

            int c = idx(s[i]);

            if(!ch[u][c]) ch[u][c] = newNode();

            u = ch[u][c];

        }

        pos[ID] = u;

    }

    void build() {

        queue<int> que;

        for(int c = ; c < sz; c++) {

            int v = ch[][c];

            if(!v) ch[][c] = ;

            else f[v] = , que.push(v);

        }

        while(!que.empty()) {

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

            for(int c = ; c < sz; c++) {

                int v = ch[u][c];

                if(!v) ch[u][c] = ch[f[u]][c];

                else f[v] = ch[f[u]][c], que.push(v);

            }

        }

    }

    void solve(char *s) {

        queue<int> que;

        memset(d, -, sizeof(d));

        int u = ;

        d[u] = ; que.push(u);

        for(int i = ; s[i]; i++) {

            int c = idx(s[i]);

            u = ch[u][c];

            int p = u;

            while(p && d[p] == -) {

                d[p] = ; que.push(p); p = f[p];

            }

        }

        while(!que.empty()) {

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

            for(int c = ; c < sz; c++) {

                int v = ch[u][c];

                if(d[v] != -) continue;

                d[v] = d[u] + ;

                que.push(v);

            }

        }

        for(int i = ; i <= m; i++) printf("%d\n", len[i] - d[pos[i]]);

    }

} ac();

int main() {

    ac.init();

    scanf("%d%d", &n, &m);

    scanf("%s", s);

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

        scanf("%s", t);

        ac.addStr(t, i);

        len[i] = strlen(t);

    }

    ac.build();

    ac.solve(s);

    return ;

}

/*

*/