是男人就過八題A_A String Game

題意

給一個字元串\(s\)，和\(n\)個子串\(t[i]\)，兩個人博弈，每次取出一個串\(t[i]\)，在後面加入一個字元，保證新字元串仍然是\(s\)的子串，無法操作的人輸。

分析

• n個子串，類比于n堆石子，如果把子串\(t[i]\)在後面加若幹字元能生成的子串看出一個狀态，用一個數表示，那每次狀态的變化，就類比于對一堆石子取走若幹個，無法操作，就類比于沒有石子可以取。
• 多堆取石子遊戲的做法就是把每堆石子的SG值(sg(x)=x)異或起來，不為零就先手赢，否則後手赢。
• 是以可以将題目轉化為求每個子串\(t[i]\)對應狀态的SG值。
• 然後就是字尾自動機的套路，每個子串就可以對應SAM上的一個節點，是以可以直接dfs記憶化搜尋SG值。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
char s[N];
int n;
struct SAM{
    int nex[N*2][26],fa[N*2],len[N*2],num[N*2];
    int cnt,lst;
    int sg[N*2];
    int newnode(int l,int s){
        for(int i=0;i<26;i++){
            nex[cnt][i]=0;
        }
        len[cnt]=l;
        num[cnt]=s;
        return cnt++;
    }
    void init(){
        cnt=0;
        lst=newnode(0,0);
        fa[lst]=-1;
        memset(sg,-1,sizeof(sg));
    }
    void add(int c){
        c-=\'a\';
        int p=lst;
        int cur=newnode(len[p]+1,1);
        while(p!=-1 && !nex[p][c]){
            nex[p][c]=cur;
            p=fa[p];
        }
        if(p==-1){
            fa[cur]=0;
        }else{
            int q=nex[p][c];
            if(len[q]==len[p]+1){
                fa[cur]=q;
            }else{
                int cl=newnode(len[p]+1,0);
                fa[cl]=fa[q];
                memcpy(nex[cl],nex[q],sizeof(nex[cl]));
                while(p!=-1 && nex[p][c]==q){
                    nex[p][c]=cl;
                    p=fa[p];
                }
                fa[q]=fa[cur]=cl;
            }
        }
        lst=cur;
    }
    int w[N*2],tp[N*2];
    void dfs(int u){
        int vis[30]={0};
        if(sg[u]!=-1){
            return;
        }
        for(int i=0;i<26;i++){
            int v=nex[u][i];
            if(v){
                dfs(v);
                vis[sg[v]]=1;
            }
        }
        for(int i=0;i<26;i++){
            if(!vis[i]){
                sg[u]=i;
                break;
            }
        }
    }
    void sfd(int l){
        for(int i=0;i<=l;i++){
            w[i]=0;
        }
        for(int i=1;i<=cnt;i++){
            w[len[i]]++;
        }
        for(int i=2;i<=l;i++){
            w[i]+=w[i-1];
        }
        for(int i=cnt-1;i>=1;i--){
            tp[w[len[i]]--]=i;
        }
        sg[lst]=0;
        int vis[30]={0};
        for(int i=cnt-1;i>=0;i--){
            int u=tp[i];
            memset(vis,0,sizeof(vis));
            for(int j=0;j<26;j++){
                int v=nex[u][j];
                if(v){
                    vis[sg[v]]=1;
                }
            }
            for(int j=0;j<26;j++){
                if(!vis[j]){
                    sg[u]=j;
                    break;
                }
            }
        }
    }
    int solve(char *s){
        int rt=0;
        int l=strlen(s);
        for(int j=0;j<l;j++){
            rt=nex[rt][s[j]-\'a\'];
        }
        return sg[rt];
    }
}ac;
int main(){
    // freopen("in.txt","r",stdin);
    while(~scanf("%s",s)){
        ac.init();
        int len=strlen(s);
        for(int i=0;i<len;i++){
            ac.add(s[i]);
        }
        //dfs或者拓撲排序求sg函數
        // ac.dfs(0);
        ac.sfd(len);
        scanf("%d",&n);
        int ans=0;
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            ans^=ac.solve(s);
        }
        if(ans){
            printf("Alice\n");
        }else{
            printf("Bob\n");
        }
    }
    return 0;
}