题解 P3883 【[JLOI2008]棋局定式】

SuperJvRuo · 2018-03-10 09:48:12 · 题解

乍一看字符集是所有的走法，应该是6*8*8*2的大小，但其实字符集应该是可能出现的所有单个字符共6+8+8+1，这样就可以直接用AC自动机了，速度与后缀数组做法基本相当，但是空间占用要大一些

#include<iostream>
#include<queue>
#include<string>
using namespace std;

int trans[128];
int cnt=0;
void init()
{
    //建立字符到整数的映射
    int cnt=0;
    trans['K']=++cnt;
    trans['Q']=++cnt;
    trans['B']=++cnt;
    trans['N']=++cnt;
    trans['R']=++cnt;
    trans['P']=++cnt;
    trans['x']=++cnt;
    trans[0]=++cnt;
    for(char i='a';i<='h';++i)
    {
        trans[i]=++cnt;
    }
    for(char i='1';i<='8';++i)
    {
        trans[i]=++cnt;
    }
}

string name[2005];
//定式名
bool vis[2005];
//是否出现

struct Tree
{
    int fail;
    int vis[26];
    int num;
}AC[800005];
//Trie树

inline void Build(string s,int num)
{
    //建树
    int l=s.length();
    int now=0;
    for(int i=0;i<l;++i)
    {
        if(AC[now].vis[trans[s[i]]]==0)
        AC[now].vis[trans[s[i]]]=++cnt;
        now=AC[now].vis[trans[s[i]]];
    }
    AC[now].num=num;
}

void Get_fail()
{
    //BFS求fail
    queue<int> Q;
    for(int i=0;i<26;++i)
    {
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;
            Q.push(AC[0].vis[i]);
        }
    }
    while(!Q.empty()) 
    {
        int u=Q.front();
        Q.pop();
        for(int i=0;i<26;++i)
        {
            if(AC[u].vis[i]!=0)
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                Q.push(AC[u].vis[i]);
            }
            else
            AC[u].vis[i]=AC[AC[u].fail].vis[i];
        }
    }
}

void AC_Query(string s)
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;++i)
    {
        now=AC[now].vis[trans[s[i]]];
        for(int t=now;t;t=AC[t].fail)
        {
            vis[AC[t].num]=1;
        } 
    }
}

int main()
{
    init();
    ios::sync_with_stdio(false);
    int n,m,k;
    string s;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        string now;
        cin>>k;
        //读入k以后还没有换行，此处需要getline一下
        getline(cin,name[i]);
        getline(cin,name[i]);
        for(int j=0;j<k;++j)
        {
            cin>>s;
            now+=s;
            //全都接起来
        }
        Build(now,i);
    }
    AC[0].fail=0;
    Get_fail();

    string now;
    for(int i=0;i<m;++i)
    {
        cin>>s;
        now+=s;
        //接起来
    }
    AC_Query(now);
    //匹配
    for(int i=1;i<=n;++i)
    {
        if(vis[i])
        cout<<name[i]<<'\n';
    }
    return 0;
}