终于完成进度男人1/8，为了这题学了sam= =
题意先有一个串，n个子串，两个人轮流每次在子串上加字符，要求加完后还是原串的子串，最后不能加的就是输者，求赢的人
解法：sam之后在构造的状态图上跑sg函数，这题的sg状态不会超过26，所以直接枚举所有状态即可，然后记忆化搜索求sg函数，最后异或起来就是答案了
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000ll #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=200000+10,maxn=100000+10;//,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; char s[N],p[N]; struct SAM{ int last,cnt; int ch[N<<1][26],fa[N<<1],l[N<<1]; int sg[N<<1]; void ins(int c){ int p=last,np=++cnt;last=np;l[np]=l[p]+1; for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(l[p]+1==l[q])fa[np]=q; else{ int nq=++cnt;l[nq]=l[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[nq]=fa[q];fa[q]=fa[np]=nq; for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq; } } } void build(){ memset(ch,0,sizeof ch); memset(fa,0,sizeof fa); memset(l,0,sizeof l); memset(sg,-1,sizeof sg); int len=strlen(s+1); last=cnt=1; for(int i=1;i<=len;i++)ins(s[i]-'a'); getsg(1); // debug(); } void debug() { for(int i=1;i<=cnt;i++) { printf("%d ",i); for(int j=0;j<26;j++) printf("%d ",ch[i][j]); printf("---%d %d %d ",fa[i],sg[i],l[i]); } } int getsg(int now) { if(sg[now]!=-1)return sg[now]; bool vis[31]; for(int i=0;i<=30;i++)vis[i]=0; for(int i=0;i<26;i++) { if(ch[now][i]) { if(sg[ch[now][i]]==-1)getsg(ch[now][i]); vis[sg[ch[now][i]]]=1; } } for(int i=0;i<=30;i++) { if(!vis[i]) { sg[now]=i; return sg[now]; } } return sg[now]; } int calsg() { int len=strlen(p+1),now=1; for(int i=1;i<=len;i++) now=ch[now][p[i]-'a']; return sg[now]; } }sam; int main() { while(~scanf("%s",s+1)) { sam.build(); int n; scanf("%d",&n); int x=0; for(int i=0;i<n;i++) { scanf("%s",p+1); x^=sam.calsg(); } if(x)puts("Alice"); else puts("Bob"); } return 0; } /******************** ********************/