# 计蒜客A1623 A String Game（后缀自动机next指针dag上跑sg函数）

sb套路题，字串显然直接把后缀自动机建出来，由于后缀自动机就是一个DAG，所以每次加一个字母可以认为是在图上点的转移，直接算出后缀自动机上每个点的sg函数值，将字串代入求亦或和即可。

```#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int,int> pii;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rept(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define de(x) cout<< #x<<" = "<<x<<"\n"
#define dd(x) cout<< #x<<" = "<<x<<" "
#define debug() cout<<"I love Miyamizu Mitsuha forever!\n"
#define mes(a,b) memset(a,b,sizeof a)
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
class SAM
{
public:
ll len[maxn<<1];
vector<int> v[maxn<<1];
int degree[maxn<<1],sg[maxn<<1];
queue<int> q;
bool vis[30];
int sz,last;
SAM()
{
sz=0,last=0;
}
void init()
{
rept(i,0,sz)
{
rep(j,0,26) next[i][j]=0;
}
sz=last=0;
len[0]=0;
}
void extend(int c)
{
int cur=++sz;
len[cur]=len[last]+1;
int p=last;
while(p!=-1&&!next[p][c])
{
next[p][c]=cur;
}
else
{
int q=next[p][c];
else
{
int clone=++sz;
len[clone]=len[p]+1;
for(int i=0;i<26;i++) next[clone][i]=next[q][i];
while(p!=-1&&next[p][c]==q)
{
next[p][c]=clone;
}
}
}
last=cur;
}
void getsg()
{
rept(i,0,sz) v[i].clear(),degree[i]=0;
rept(i,0,sz)
{
rep(j,0,26)
{
if(next[i][j])
{
v[next[i][j]].pb(i);
degree[i]++;
}
}
}
while(!q.empty()) q.pop();
q.push(last);
while(!q.empty())
{
int x=q.front();
q.pop();
rep(i,0,v[x].size())
{
degree[v[x][i]]--;
if(!degree[v[x][i]]) q.push(v[x][i]);
}
rept(i,0,26) vis[i]=0;
rep(i,0,26) if(next[x][i]) vis[sg[next[x][i]]]=1;
sg[x]=0;
while(vis[sg[x]]) sg[x]++;
}
}
int getval(string s)
{
int pos=0;
rep(i,0,s.size()) pos=next[pos][s[i]-‘a‘];
return sg[pos];
}
}sam;
string s;

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
while(cin>>s)
{
sam.init();
rep(i,0,s.size())
{
sam.extend(s[i]-‘a‘);
}
sam.getsg();
int n,val=0;
cin>>n;
string t;
rep(i,0,n)
{
cin>>t;
val^=sam.getval(t);
}
if(val) cout<<"Alice\n";
else cout<<"Bob\n";
}
return 0;
}```

(0)
(0)