是男人就过 8 题--Pony.AI 题 - A String Game
题意：给一个串t以及n个t的子串s，两个人每轮可以选择一个s在他的后边添加一个字符满足得到的新串仍是t的子串，第一个不能操作的人输。
做法：对s串建SAM，在一个子串后边添加字符，等价于在SAM上向后移动一步，预处理每个状态的sg函数，将n个子串的答案异或起来。SAM空间要开两倍（女装警告～～
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
const int N = 2e5 + 7;
typedef long long ll;
using namespace std;
struct SAM {
int n, step[N], fa[N], num[N], last, root, cnt;
char s[N];
map<char , int> ch[N];
void init() {
for(int i = 0; i <= cnt; ++i) ch[i].clear();
cnt = 0; last = root = ++cnt;
}
void add(int x) {
int tmp = s[x], p = last, np = ++cnt;
step[last = np] = x;
while(p && !ch[p][tmp]) ch[p][tmp] = np, p =fa[p];
if(!p) fa[np] = root;
else {
int q = ch[p][tmp];
if(step[q] == step[p] + 1) fa[np] = q;
else {
int nq = ++ cnt; step[nq] = step[p] + 1;
ch[nq] = ch[q];
fa[nq] = fa[q], fa[q] = fa[np] = nq;
while(ch[p][tmp] == q) ch[p][tmp] = nq, p = fa[p];
}
}
}
int A[N], sg[N], vis[N];
void init_sg() {
memset(A, 0 , sizeof(A));
memset(sg, 0 , sizeof(sg));
memset(vis, 0 , sizeof(vis));
for(int i = 1; i <= cnt; ++i) ++ A[step[i]];
for(int i = 1; i <= n; ++i) A[i] += A[i-1];
for(int i = cnt; i; --i) num[A[step[i]]--] = i;
for(int i = cnt; i; --i) {
for(auto x: ch[num[i]]) {
int t = x.second;
vis[sg[t]] = num[i];
}
for(int j = 0; ; ++j) if(vis[j] != num[i]) {
sg[num[i]] = j; break;
}
}
}
int cal_sg(char str[]) {
int len = strlen(str+1), now = root;
for(int i = 1; i <= len; ++i) now = ch[now][str[i]];
return sg[now];
}
void run() {
init();
for(int i = 1; i <= n; ++i) add(i);
init_sg();
}
} Fe;
char str[N];
int main() {
while(scanf(" %s",Fe.s+1) != EOF) {
Fe.n = strlen(Fe.s+1);
Fe.run(); int n;
scanf("%d",&n);
int ans = 0;
rep(i, 1, n) {
scanf(" %s",str+1);
ans ^= Fe.cal_sg(str);
}
puts(ans ? "Alice" : "Bob");
}
return 0;
}