AStringGame

用sam跑出DAG图，再求出sg值。
SG定理：n个有向图游戏组成的组合游戏当且仅当SG值异或和等于0时先手必输，否则先手必胜。

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#ifdef LOCAL
#define debug(x) cout << "[" __FUNCTION__ ": " #x " = " << (x) << "]\n"
#define TIME cout << "RuningTime: " << clock() << "ms\n", 0
#else
#define TIME 0
#endif
#define hash_ 1000000009
#define Continue(x) { x; continue; }
#define Break(x) { x; break; }
const int mod = 998244353;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define gc p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
inline int read(){ static char buf[1000000], *p1 = buf, *p2 = buf; register int x = false; register char ch = gc; register bool sgn = false; while (ch != '-' && (ch < '0' || ch > '9')) ch = gc; if (ch == '-') sgn = true, ch = gc; while (ch >= '0'&& ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc; return sgn ? -x : x; }
ll fpow(ll a, int b, int mod) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; }
int len[N << 1];
int lnk[N << 1];
int cnt[N << 1];
int nxt[N << 1][26];
int idx;
int last;
ll sub[N << 1];
char s[N];
int sg[N << 1];
void init()
{
    last = idx = 1;
    lnk[1] = len[1] = 0;
}
void clear()
{
    memset(len, 0, sizeof len);
    memset(lnk, 0, sizeof lnk);
    memset(cnt, 0, sizeof cnt);
    memset(nxt, 0, sizeof nxt);
}
void extend(int c)
{
    int x = ++idx;
    len[x] = len[last] + 1;
    sub[x] = 1;
    int p;
    for (p = last; p && !nxt[p][c]; p = lnk[p])
        nxt[p][c] = x;
    if (!p)
        lnk[x] = 1, cnt[1]++;
    else
    {
        int q = nxt[p][c];
        if (len[p] + 1 == len[q])
            lnk[x] = q, cnt[q]++;
        else
        {
            int nq = ++idx;
            len[nq] = len[p] + 1;
            lnk[nq] = lnk[q];
            memcpy(nxt[nq], nxt[q], sizeof nxt[q]);
            for (; p && nxt[p][c] == q; p = lnk[p])
                nxt[p][c] = nq;
            lnk[q] = lnk[x] = nq;
            cnt[nq] += 2;
        }
    }
    last = x;
}
void dfs(int x)
{
    if (sg[x] != -1)
        return;
    int vis[26] = { 0 };
    for (int i = 0; i < 26; i++)
    {
        if (nxt[x][i])
        {
            dfs(nxt[x][i]);
            vis[sg[nxt[x][i]]] = 1;
        }
    }
    for (int i = 0; i < 26; i++) //mex
        if (!vis[i])
            Break(sg[x] = i)
}
int main()
{
#ifdef LOCAL
    freopen("E:/input.txt", "r", stdin);
#endif
    while (~scanf("%s", s + 1))
    {
        clear();
        init();
        memset(sg, -1, sizeof sg);
        int len = strlen(s + 1);
        for (int i = 1; i <= len; i++)
            extend(s[i] - 'a');
        dfs(1);
        int sum = 0;
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", s + 1);
            int len = strlen(s + 1);
            int rk = 1;
            for (int j = 1; j <= len; j++)
            {
                rk = nxt[rk][s[j] - 'a'];
            }
            sum ^= sg[rk];
        }
        if (sum)
            puts("Alice");
        else
            puts("Bob");
    }
    return TIME;
}