P5231 [JSOI2012]玄武密码

分析：

　　首先对所有询问串建立AC自动机，然后扫描一遍母串，在AC自动机上走，没走到一个点，标记这个点走过了，并且它的fail树上的祖先节点也可以访问到（即可以匹配到主串），于是沿着fail树打标记，当到一个已经打过标记的点的时候，退出。这样保证每个点只会被打标机一次。询问时，在AC自动机上倒着往前走，走到第一个打过标记的点的时候，从AC自动机的根节点到这个点的距离就是答案。复杂度$O(N+100M)$。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int SZ = , N = ;

int id[], len[N], pos[N], ch[SZ][], fa[SZ], q[SZ], fail[SZ], Index;

bool vis[SZ];

char s[SZ], t[];

void Insert(char *s,int k) {

    int u = ;

    for (int i = ; i <= len[k]; ++i) {

        int c = id[(int)s[i]];

        if (!ch[u][c]) ch[u][c] = ++Index, fa[Index] = u;

        u = ch[u][c];

    }

    pos[k] = u;

}

void bfs() {

    int L = , R = ;

    for (int i = ; i <= ; ++i) if (ch[][i]) q[++R] = ch[][i];

    while (L <= R) {

        int u = q[L ++];

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

            int v = ch[u][c];

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

            else fail[v] = ch[fail[u]][c], q[++R] = v;

        }

    }

}

int Calc(int x) {

    int ans = len[x];

    for (int i = pos[x]; i; i = fa[i], ans --)

        if (vis[i]) return ans;

}

int main() {

    int n = read(), m = read();

    id['E'] = , id['S'] = , id['W'] = , id['N'] = ;

    scanf("%s", s + );

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

        scanf("%s", t + );

        len[i] = strlen(t + );

        Insert(t, i);

    }

    bfs();

    int u = , v;

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

        int c = id[(int)s[i]];

        u = ch[u][c];

        v = u;

        while (v && !vis[v]) vis[v] = , v = fail[v];

    }

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

        printf("%d\n", Calc(i));

    return ;

}

巴特西

P5231 [JSOI2012]玄武密码

P5231 [JSOI2012]玄武密码

最新文章

热门文章