给一个字符串\(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; }