[计蒜客][是男人就过 8 题--Pony.AI 题] A String Game

        题目链接：https://nanti.jisuanke.com/t/24852

        题目大意：给出模板串\(T\)和\(n\)个\(T\)的子串\(S_i\)，两个人轮流选择一个子串\(S_i\)，在它的后面加一个字符，使得变化后的\(S_i\)仍然为\(T\)的子串，无法操作的人失败，Alice先手Bob后手，两个人都足够聪明，问谁获胜。（\(|T|\leq 10^5\)，字符串总长不超过\(3 \cdot 10^7\)）

        题解：这个是个典型的nim博弈问题，对模板串建后缀自动机，然后在后缀自动机上算SG函数，每次算\(S_i\)的SG值只要从后缀自动机的root沿着边走到对应位置取它的SG值就好了。最后把每个子串的SG值异或，如果为正则Alice必胜。由于还不是很懂sg函数，先暂时这么放着。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e5+10;

struct Suffix_Auto_Maton
{
    struct State
    {
        int next[26],link,len;
    }st[maxn<<1];
 
    int last,cnt;
	int SG[maxn<<1];

	void clear(State *x)
	{
		x->link=x->len=0;
		memset(x->next,0,sizeof(x->next));
	}
	void init() {last=cnt=1;memset(SG,0xFF,sizeof(SG));clear(&st[1]);}
 
    void insert(int c)
    {
        int x=++cnt,p;
		clear(&st[cnt]);
        st[x].len=st[last].len+1;
        for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
        if (!p) st[x].link=1;
        else {
            int q=st[p].next[c];
            if (st[p].len+1==st[q].len) st[x].link=q;
            else {
                int v=++cnt;
				clear(&st[cnt]);
                st[v].len=st[p].len+1;
                memcpy(st[v].next,st[q].next,sizeof(st[v].next));
                st[v].link=st[q].link;
                for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
                st[q].link=st[x].link=v;
            }
        }
        last=x;
    }

	int Get_SG(int x)
    {
        if (SG[x]>=0) return SG[x];
        int q[26],qnum=0;
        for (int i=0;i<26;i++) if (st[x].next[i]) q[qnum++]=Get_SG(st[x].next[i]);
        sort(q,q+qnum);
        SG[x]=0;
        for (int i=0;i<qnum;i++) if (SG[x]==q[i]) SG[x]++;
        return SG[x];
    }

	int sg(char *s)
	{
		int len=strlen(s);
		int x=1;
		for (int i=0;i<len;i++) x=st[x].next[s[i]-'a'];
		return Get_SG(x);
	}
}S;

char t[maxn],s[maxn];
int n,ans,length;

int main()
{
	while (scanf("%s",t)!=EOF)
	{
		scanf("%d",&n);
		length=strlen(t);
		S.init();
		for (int i=0;i<length;i++)
			S.insert(t[i]-'a');
		ans=0;
		while (n--)
			scanf("%s",s),ans^=S.sg(s);
		printf("%s\n",(ans>0)?"Alice":"Bob");
	}
	return 0;
}